oj.uz

Submission #80295

# Submission time Handle Problem Language Result Execution time Memory
80295 2018-10-19T20:21:55 Z mbvdk Usmjeri (COCI17_usmjeri) C++14
140 / 140
 1358 ms 162356 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<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, 2);
			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-q1);	
			}
			else if(q1 == q2){
				ok = 0;
			}
			else{
				hld.update_up(a[idx], u, q1);
				hld.update_up(b[idx], u, q2);
			}
		}
	}
	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);
}
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<dp[u].size();i++){
              ~^~~~~~~~~~~~~
usmjeri.cpp:224:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<hld.g[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]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 85052 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 945 ms 162356 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 162356 KB Output is correct
2 Correct 34 ms 162356 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 162356 KB Output is correct
2 Correct 39 ms 162356 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 162356 KB Output is correct
2 Correct 38 ms 162356 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 162356 KB Output is correct
2 Correct 39 ms 162356 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1313 ms 162356 KB Output is correct
2 Correct 1308 ms 162356 KB Output is correct
3 Correct 544 ms 162356 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1201 ms 162356 KB Output is correct
2 Correct 1134 ms 162356 KB Output is correct
3 Correct 858 ms 162356 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1185 ms 162356 KB Output is correct
2 Correct 1358 ms 162356 KB Output is correct
3 Correct 833 ms 162356 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1232 ms 162356 KB Output is correct
2 Correct 1170 ms 162356 KB Output is correct
3 Correct 509 ms 162356 KB Output is correct