| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 80293 |
2018-10-19T19:59:15 Z |
mbvdk |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
1156 ms |
167992 KB |
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int N = 300000;
typedef long long ll;
typedef pair<int, int> pii;
int p[N+5];
int find(int a){
return p[a] == a?a:(p[a]=find(p[a]));
}
void uni(int a, int b){
a = find(a), b = find(b);
if(a != b) p[a] = b;
}
struct hld{
vector<pii> g[N+5];
int chainIdx[N+5];
int chainHead[N+5];
int baseArr[N+5];
int posArr[N+5];
int chainNo = 1;
int idx = 1;
int depth[N+5];
int par[20][N+5];
int ss[N+5];
int st[4*N+5];
int lazy[4*N+5];
int n = N;
void init(int m){
n = m;
chainNo = 1;
idx = 1;
for(int i=1;i<=n;i++){
g[i].clear();
chainIdx[i] = 0;
chainHead[i] = 0;
baseArr[i] = 0;
posArr[i] = 0;
g[i].clear();
for(int j=0;j<20;j++) par[j][i] = 0;
}
}
void build(int n, int s, int e){
if(s == e) st[n] = baseArr[s];
else{
int mid = (s+e)/2;
build(n*2, s, mid);
build(n*2+1, mid+1, e);
st[n] = max(st[n*2], st[n*2+1]);
}
}
void update(int n, int s, int e, int l, int r, int v){
if(lazy[n]){
st[n] |= lazy[n];
if(s != e){
lazy[n+n] |= lazy[n];
lazy[n+n+1] |= lazy[n];
}
lazy[n] = 0;
}
if(s > r || l > e) return;
if(l <= s && e <= r){
st[n] |= v;
if(s != e){
lazy[n+n] |= v;
lazy[n+n+1] |= v;
}
return;
}
int mid = (s+e)/2;
update(n*2, s, mid, l, r, v);
update(n*2+1, mid+1, e, l, r, v);
st[n] = st[n+n] | st[n+n+1];
}
int query(int n, int s, int e, int l, int r){
if(lazy[n]){
st[n] |= lazy[n];
if(s != e){
lazy[n+n] |= lazy[n];
lazy[n+n+1] |= lazy[n];
}
lazy[n] = 0;
}
if(s > r || l > e) return 0;
if(l <= s && e <= r) return st[n];
int mid = (s+e)/2;
int p1 = query(n*2, s, mid, l, r);
int p2 = query(n*2+1, mid+1, e, l, r);
return p1 | p2;
}
int LCA(int a, int b){
if(depth[a] < depth[b]) swap(a, b);
int diff = depth[a] - depth[b];
for(int i=19;i>=0;i--){
if((diff>>i)&1) a = par[i][a];
}
if(a == b) return a;
for(int i=19;i>=0;i--){
if(par[i][a] != par[i][b]) a = par[i][a], b = par[i][b];
}
return par[0][a];
}
void addEdge(int a, int b, int c){
g[a].push_back(pii(b, c));
g[b].push_back(pii(a, c));
}
void dfs(int u, int p, int d){
depth[u] = d;
par[0][u] = p;
ss[u] = 1;
for(int i=0;i<g[u].size();i++){
int v = g[u][i].first;
if(v == p) continue;
dfs(v, u, d+1);
ss[u] += ss[v];
}
}
void decompose(int u, int p, int c){
if(chainHead[chainNo] == 0) chainHead[chainNo] = u;
chainIdx[u] = chainNo;
posArr[u] = idx;
baseArr[idx++] = c;
int nc = 0, pos = -1, sz = 0;
for(int i=0;i<g[u].size();i++){
int v = g[u][i].first;
int w = g[u][i].second;
if(v == p) continue;
if(ss[v] > sz){
sz = ss[v];
pos = v;
nc = w;
}
}
if(pos != -1) decompose(pos, u, nc);
for(int i=0;i<g[u].size();i++){
int v = g[u][i].first;
int w = g[u][i].second;
if(v == p || v == pos) continue;
chainNo++;
decompose(v, u, w);
}
}
int query_up(int u, int v){
int res = 0;
while(1){
int uchain = chainIdx[u];
int vchain = chainIdx[v];
if(uchain == vchain){
if(u != v) res = res|query(1, 1, idx, posArr[v]+1, posArr[u]);
break;
}
res = res|query(1, 1, idx, posArr[chainHead[uchain]], posArr[u]);
u = chainHead[uchain];
u = par[0][u];
}
return res;
}
void update_up(int u, int v, int val){
while(1){
int uchain = chainIdx[u];
int vchain = chainIdx[v];
if(uchain == vchain){
if(u != v) update(1, 1, idx, posArr[v]+1, posArr[u], val);
break;
}
update(1, 1, idx, posArr[chainHead[uchain]], posArr[u], val);
u = chainHead[uchain];
u = par[0][u];
}
}
void getParent(){
for(int j=1;j<=19;j++){
for(int i=1;i<=n;i++){
if(par[j-1][i] != 0) par[j][i] = par[j-1][par[j-1][i]];
}
}
}
}hld;
vector<int> dp[300005];
int a[300005], b[300005];
ll ans = 0;
bool ok = 1;
vector<int> ins[300005];
set<int> dp3[300005];
set<int>::iterator its;
void dfs(int u, int p){
for(int i=0;i<hld.g[u].size();i++){
int v = hld.g[u][i].first;
if(v == p) continue;
dfs(v, u);
if(dp3[u].size() < dp3[v].size()){
swap(dp3[u], dp3[v]);
}
for(its = dp3[v].begin();its != dp3[v].end();its++){
dp3[u].insert(*its);
}
}
while(!dp3[u].empty() && -*dp3[u].begin() == hld.depth[u]-1){
dp3[u].erase(dp3[u].begin());
}
if(!dp3[u].empty()) uni(u, p);
for(int i=0;i<dp[u].size();i++){
int idx = dp[u][i];
if(u == a[idx]){
int q1 = hld.query_up(b[idx], u);
if(q1 == 0) hld.update_up(b[idx], u, 1);
else if(q1 == 1) hld.update_up(b[idx], u, 1);
else if(q1 == 2) hld.update_up(b[idx], u, 2);
else ok = 0;
}
else{
int q1 = hld.query_up(a[idx], u);
int q2 = hld.query_up(b[idx], u);
if(q1 == 3 || q2 == 3){
ok = 0;
}
else if(q1 == 0 && q2 == 0){
hld.update_up(a[idx], u, 1);
hld.update_up(b[idx], u, 2);
}
else if(q1 == 0){
hld.update_up(a[idx], u, 3-q2);
hld.update_up(b[idx], u, q2);
}
else if(q2 == 0){
hld.update_up(a[idx], u, q1);
hld.update_up(b[idx], u, 3-q2);
}
else if(q1 == q2){
ok = 0;
}
else{
hld.update_up(a[idx], u, q1);
hld.update_up(b[idx], u, q2);
}
}
}
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
hld.init(n);
for(int i=2;i<=n;i++){
int a, b;
scanf("%d%d", &a, &b);
hld.addEdge(a, b, 0);
p[i] = i;
}
hld.dfs(1, 0, 0);
hld.getParent();
hld.decompose(1, 0, 0);
hld.build(1, 1, hld.idx);
for(int i=1;i<=m;i++){
scanf("%d%d", &a[i], &b[i]);
int lca = hld.LCA(a[i], b[i]);
if(lca == b[i]) swap(a[i], b[i]);
dp[lca].emplace_back(i);
if(lca == a[i]){
dp3[b[i]].insert(-hld.depth[lca]);
}
else{
uni(a[i], b[i]);
dp3[a[i]].insert(-hld.depth[lca]);
dp3[b[i]].insert(-hld.depth[lca]);
}
}
dfs(1, 0);
if(!ok) printf("0\n");
else{
ll ans = 1;
for(int i=2;i<=n;i++){
int p = hld.posArr[i];
int q = hld.query(1, 1, hld.idx, p, p);
if(find(i) == i) ans = (ans*2)%mod;
}
printf("%lld\n", ans);
}
}
Compilation message
usmjeri.cpp: In member function 'void hld::dfs(int, int, int)':
usmjeri.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++){
~^~~~~~~~~~~~
usmjeri.cpp: In member function 'void hld::decompose(int, int, int)':
usmjeri.cpp:124:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++){
~^~~~~~~~~~~~
usmjeri.cpp:135:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++){
~^~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs(int, int)':
usmjeri.cpp:188:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<hld.g[u].size();i++){
~^~~~~~~~~~~~~~~~
usmjeri.cpp:203:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dp[u].size();i++){
~^~~~~~~~~~~~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:275:8: warning: unused variable 'q' [-Wunused-variable]
int q = hld.query(1, 1, hld.idx, p, p);
^
usmjeri.cpp:242:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
usmjeri.cpp:246:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
usmjeri.cpp:255:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a[i], &b[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
539 ms |
86580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
958 ms |
167992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
167992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
167992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
167992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
167992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1156 ms |
167992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
907 ms |
167992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
838 ms |
167992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
860 ms |
167992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
