| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 235753 |
2020-05-29T15:10:28 Z |
VEGAnn |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
685 ms |
88928 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], chk[N];
queue<int> q;
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], p1[N], p2[N];
bool mrk[N], chkd[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]++;
int PR = pra(y, x);
ad[PR]--;
p1[i] = PR;
} else {
ad[x]++;
ad[y]++;
int pr1 = pra(x, y);
int pr2 = pra(y, x);
ad[pr1]--;
ad[pr2]--;
pr[pr1] = get(pr2);
p1[i] = pr1;
p2[i] = pr2;
}
}
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;
}
fill(mrk, mrk + n, 0);
fill(chkd, chkd + n, 0);
for (int it = 0; it < m; ){
int j = it;
while (j < m && LC[NM[j]] == LC[NM[it]]) {
int i = NM[j];
if (U[i] == LC[i]){
chk[p1[i]].PB(i);
} else {
chk[p1[i]].PB(i);
chk[p2[i]].PB(i);
}
j++;
}
int lc = LC[NM[it]];
for (int u : g[lc]){
if (u == up[lc][0]) continue;
if (mrk[u]) continue;
q.push(u);
mrk[u] = 1;
while (sz(q)){
int v = q.front(); q.pop();
for (int i : chk[v]){
if (chkd[i]) continue;
chkd[i] = 1;
if (U[i] != LC[i]){
int nw = (p1[i] == v ? p2[i] : p1[i]);
if (!mrk[nw]){
mrk[nw] = 1;
q.push(nw);
}
}
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]);
}
}
}
}
}
}
it = j;
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
43308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
395 ms |
88928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14848 KB |
Output is correct |
| 2 |
Correct |
13 ms |
14848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14848 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
15616 KB |
Output is correct |
| 2 |
Correct |
15 ms |
15360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
15616 KB |
Output is correct |
| 2 |
Correct |
16 ms |
15360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
540 ms |
72320 KB |
Output is correct |
| 2 |
Correct |
604 ms |
72520 KB |
Output is correct |
| 3 |
Correct |
322 ms |
49616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
685 ms |
74020 KB |
Output is correct |
| 2 |
Correct |
653 ms |
73796 KB |
Output is correct |
| 3 |
Correct |
426 ms |
54508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
641 ms |
74140 KB |
Output is correct |
| 2 |
Correct |
574 ms |
72564 KB |
Output is correct |
| 3 |
Correct |
436 ms |
54248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
597 ms |
74340 KB |
Output is correct |
| 2 |
Correct |
607 ms |
74724 KB |
Output is correct |
| 3 |
Correct |
290 ms |
48120 KB |
Output is correct |
