| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 235525 |
2020-05-28T12:18:38 Z |
VEGAnn |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
760 ms |
71160 KB |
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
#define ft first
#define sd second
#define PB push_back
#define pli pair<ll,int>
using namespace std;
typedef long long ll;
const int N = 300100;
const int PW = 20;
const int oo = 2e9;
const int md = int(1e9) + 7;
vector<int> g[N];
int n, m, pr[N], ans = 1, up[N][PW], tin[N], tout[N], tt = 0, ad[N];
int V[N], NM[N], U[N], LC[N], fen[2][N], h[N], col[N];
bool mrk[N];
int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); }
void dfs(int v, int p){
up[v][0] = p;
for (int po = 1; po < PW; po++)
up[v][po] = up[up[v][po - 1]][po - 1];
tin[v] = ++tt;
for (int u : g[v]){
if (p == u) continue;
h[u] = h[v] + 1;
dfs(u, v);
}
tout[v] = tt;
}
bool upper(int a, int b){
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b){
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int po = PW - 1; po >= 0; po--)
if (!upper(up[a][po], b))
a = up[a][po];
return up[a][0];
}
int pra(int a, int b){
for (int po = PW - 1; po >= 0; po--)
if (!upper(up[a][po], b))
a = up[a][po];
return a;
}
void DFS(int v){
for (int u : g[v]){
if (u == up[v][0]) continue;
DFS(u);
ad[v] += ad[u];
}
if (ad[v] > 0)
pr[get(v)] = get(up[v][0]);
}
bool cmp(int _x, int _y){
if (h[LC[_x]] == h[LC[_y]])
return min(tin[U[_x]], tin[V[_x]]) < min(tin[U[_y]], tin[V[_y]]);
return h[LC[_x]] < h[LC[_y]];
}
int sum(int tp, int ps){
int res = 0;
for (; ps >= 0; ps = (ps & (ps + 1)) - 1)
res += fen[tp][ps];
return res;
}
void update(int tp, int ps, int vl){
for (; ps < N; ps = (ps | (ps + 1)))
fen[tp][ps] += vl;
}
void BAD(){
cout << 0;
exit(0);
}
void upd(int cl, int v, int lc){
while (col[v] < 0 && v != lc) {
update(cl, tin[v], 1);
update(cl, tout[v] + 1, -1);
col[v] = cl;
v = up[v][0];
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m;
for (int i = 1; i < n; i++){
int x, y; cin >> x >> y;
x--; y--;
g[x].PB(y);
g[y].PB(x);
pr[i] = i;
col[i] = -1;
}
dfs(0, 0);
for (int i = 0; i < m; i++){
int x, y; cin >> x >> y;
x--; y--;
int lc = lca(x, y);
LC[i] = lc;
NM[i] = i;
if (x != lc)
swap(x, y);
U[i] = x; V[i] = y;
if (x == lc){
ad[y]++;
ad[pra(y, x)]--;
} else {
ad[x]++;
ad[y]++;
ad[pra(x, y)]--;
ad[pra(y, x)]--;
pr[get(pra(x, y))] = get(pra(y, x));
}
}
DFS(0);
sort(NM, NM + m, cmp);
for (int i = 1; i < n; i++){
int cur = get(i);
if (mrk[cur]) continue;
mrk[cur] = 1;
ans += ans;
if (ans >= md)
ans -= md;
}
cerr << cmp(0, 5) << '\n';
for (int it = 0; it < m; it++){
int i = NM[it];
if (U[i] == LC[i]){
int sf = sum(0, tin[V[i]]) - sum(0, tin[LC[i]]);
int ss = sum(1, tin[V[i]]) - sum(1, tin[LC[i]]);
if (sf > 0 && ss > 0)
BAD();
if (ss == 0){
upd(0, V[i], LC[i]);
} else {
upd(1, V[i], LC[i]);
}
} else {
int ff = sum(0, tin[U[i]]) - sum(0, tin[LC[i]]);
int fs = sum(1, tin[U[i]]) - sum(1, tin[LC[i]]);
int sf = sum(0, tin[V[i]]) - sum(0, tin[LC[i]]);
int ss = sum(1, tin[V[i]]) - sum(1, tin[LC[i]]);
if (ff > 0 && fs > 0)
BAD();
if (sf > 0 && ss > 0)
BAD();
if (sf > 0 && ff > 0)
BAD();
if (ss > 0 && fs > 0)
BAD();
if (ff == 0 && sf == 0){
if (ss > 0) {
upd(1, V[i], LC[i]);
upd(0, U[i], LC[i]);
} else {
upd(0, V[i], LC[i]);
upd(1, U[i], LC[i]);
}
} else {
if (ff == 0) {
upd(0, V[i], LC[i]);
upd(1, U[i], LC[i]);
} else {
upd(1, V[i], LC[i]);
upd(0, U[i], LC[i]);
}
}
}
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
203 ms |
30456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
396 ms |
71160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
12 ms |
8320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
8320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
583 ms |
53488 KB |
Output is correct |
| 2 |
Correct |
619 ms |
53840 KB |
Output is correct |
| 3 |
Correct |
354 ms |
36744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
760 ms |
53760 KB |
Output is correct |
| 2 |
Correct |
702 ms |
53624 KB |
Output is correct |
| 3 |
Correct |
463 ms |
38264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
732 ms |
53632 KB |
Output is correct |
| 2 |
Correct |
581 ms |
53880 KB |
Output is correct |
| 3 |
Correct |
477 ms |
38264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
676 ms |
54136 KB |
Output is correct |
| 2 |
Correct |
707 ms |
54360 KB |
Output is correct |
| 3 |
Correct |
291 ms |
36168 KB |
Output is correct |
