# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
492556 |
2021-12-08T00:12:30 Z |
cgiosy |
Usmjeri (COCI17_usmjeri) |
C++17 |
|
137 ms |
34336 KB |
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD=1e9+7;
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N, M;
cin>>N>>M;
int D[N], P[N], E[N*2], F[N*2], G[N]{};
for(int i=1; i<N; i++) {
int a, b;
cin>>a>>b; --a, --b;
E[i*2]=b, F[i*2]=G[a], G[a]=i*2;
E[i*2+1]=a, F[i*2+1]=G[b], G[b]=i*2+1;
}
function<void(int)> dfs=[&](int i) {
for(int e=G[i]; e; e=F[e]) if(int&j=E[e]; j!=P[i])
D[j]=D[i]+1, P[j]=i, dfs(j);
};
D[0]=1, P[0]=0; dfs(0);
function<int(int)> root=[&](int i) { return !D[i] ? P[i]=root(P[i]) : i; };
while(M--) {
int a, b;
cin>>a>>b; --a, --b;
for(a=root(a); a!=(b=root(b)); D[b]=0) if(D[a]>D[b]) swap(a, b);
}
int v=2;
for(int i=1; i<N; i++) { int u=v+v; u=u-MOD<0 ? u : u-MOD; v=D[i] ? u : v; }
cout<<v<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
12560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
34336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
464 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
464 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
129 ms |
16744 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
16576 KB |
Output is correct |
2 |
Correct |
130 ms |
16608 KB |
Output is correct |
3 |
Incorrect |
82 ms |
11008 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
16884 KB |
Output is correct |
2 |
Incorrect |
132 ms |
16828 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
120 ms |
17224 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |