|
|
Show all threads Hide all threads Show all messages Hide all messages | Test 3 | Конобейцев Иван Олегович | 1962. In Chinese Restaurant | 7 Dec 2022 16:49 | 1 | Test 3 Конобейцев Иван Олегович 7 Dec 2022 16:49 | Тест 12 | Ilya | 1962. In Chinese Restaurant | 5 May 2021 06:44 | 1 | 2 1 2 Ответ: 1 Этот тест может быть крайним случаем в вашем решении так как уже на такой тест и схожие: 3 2 2 3 Ответ: 2 Edited by author 05.05.2021 06:45 | Where is bug? | Felix_Mate | 1962. In Chinese Restaurant | 5 Nov 2016 00:23 | 4 | #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> const long long mod=1000000007; const int nmax=200; int n,m,t,p; long long v[nmax],fact[nmax],step[nmax]; bool used[nmax]; bool a[nmax][nmax]; long long ans; void DFS(int v) { for(int j=1;j<=n;j++) { if(a[v][j] && !used[j]) { t++; used[j]=true; DFS(j); } } } bool FindCycle(int v,int pr) { bool f=false; for(int j=1;j<=n;j++) { if(a[v][j] && j!=pr) { if(used[j]) return true; else { used[j]=true; t++; f=f | FindCycle(j,v); } } } return f; } void main() { scanf("%d%d\n",&n,&m);
if(n<=2) { printf("1"); return; }
fact[0]=1; for(int i=1;i<=n;i++) fact[i]=fact[i-1]*((long long)i) % mod;
for(int i=1;i<=n;i++) step[i]=0;
for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) a[i][j]=false; }
for(int i=1;i<=m;i++) { scanf("%d\n",&t); if(!a[i][t]) { a[i][t]=a[t][i]=true; step[i]++; step[t]++;
} }
p=1; while(p<=n && step[p]<=2) p++; if(p<=n) { printf("0"); return; }
for(int i=1;i<=n;i++) used[i]=false;
for(int i=1;i<=n;i++) { if(!used[i]) { used[i]=true; t=1; if(FindCycle(i,-1)) { if(t<n) { printf("0"); return; } if(t==n) { printf("2"); return; } }
} }
for(int i=1;i<=n;i++) used[i]=false; p=0; ans=1; for(int i=1;i<=n;i++) { if(!used[i]) { p++; t=1; used[i]=true; DFS(i); if(t>1) t=2; ans*=((long long)t) % mod; } } ans=ans*fact[p-1] % mod; while(ans<0) ans+=mod; printf("%lld",ans); } Test #9 is the first test with N = 100, and it's also the first with M = 100. I've generated 2k+ random tests with those parameters but got no difference between programs, so i guess it should be a quite specific test. Anyways, the right answer to that one is 950M ± 10M, and yours is 580M ± 10M. В-общем,я в своём репертуаре. ТОТ ЖЕ ГОВНОКОД, но на ПАСКАЛЕ, дал АС! P.S. Glad to see you, Jane Soboleva!!! Oh, i guess it was something syntax-specific then, like in a certain place there goes a wrong order of operations or something like that... P.S. Glad to see you, Jane Soboleva!!! <3 | Хэлп, пипл! | Felix_Mate | 1962. In Chinese Restaurant | 19 Sep 2016 19:12 | 1 | Wa9. Хотелось бы несколько наглядных тестов или указание на ошибку в решении. Решение: 1)n<=2 => ans=1 2)n>=3; если есть вершина степени >=3 => ans=0 иначе в графе (неориентированном) есть либо циклы, либо цепи, причём они не пересекаются (т.е. от цикла ни одна цепь не отходит) а)пусть найден некоторый цикл если его длина = n => ans=2 иначе ans=0 б)циклов нет пусть p-общее число цепей в графе, len(i)-длина i цепи если len(i)>2 то положим len(i)=2 => ans=len(1)*len(2)*...*len(p)*(p-1)! Edited by author 19.09.2016 19:13 Edited by author 19.09.2016 19:34 Edited by author 29.10.2016 23:21 | WA# 12 | IgorKoval [PskovSU] | 1962. In Chinese Restaurant | 2 Sep 2013 03:44 | 1 | WA# 12 IgorKoval [PskovSU] 2 Sep 2013 03:44 Test: 2 1 2 answer: 1 Maybe your answer is 2? =) Edited by author 02.09.2013 03:44 Edited by author 02.09.2013 03:46 | B (when i>m)is not required according to a fixed position to sit? | hnust_liuwenjing | 1962. In Chinese Restaurant | 22 Jun 2013 14:03 | 1 | Edited by author 22.06.2013 14:08 |
|
|
|