oj.uz

답안 #492559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492559 2021-12-08T00:41:38 Z cgiosy Usmjeri (COCI17_usmjeri) C++17
28 / 140
 473 ms 65884 KB 
// test maruii code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
 
vector<int> edge0[300002];
vector<pii> edge[300002];
int prt[19][300002], dth[300002], par[300002];
int fnd(int x){return x==par[x]?x:par[x]=fnd(par[x]);}
void uni(int x, int y){
	x = fnd(x), y = fnd(y);
	if(x==y) return;
	if(dth[x]<dth[y]) swap(x, y);
	par[x] = y;
}
void dfs0(int x, int p){
	prt[0][x] = p;
	dth[x] = dth[p] + 1;
	for(auto i: edge0[x]){
		if(i==p) continue;
		dfs0(i, x);
	}
}
 
int lca(int x, int y){
	if(dth[x]<dth[y]) swap(x, y);
	for(int i=18; i>=0; --i) if(dth[prt[i][x]]>=dth[y]) x = prt[i][x];
	if(x==y) return x;
	for(int i=18; i>=0; --i) if(prt[i][x]!=prt[i][y]) x = prt[i][x], y = prt[i][y];
	return prt[0][x];
}
 
const int mod = 1e9+7;
bool used[300001];
int dir[300001];
bool dfs(int x, int p, int c){
	if(dir[x] != -1) return dir[x] == c;
	dir[x] = c;
	for(auto i: edge[x]){
		if(p==i.ss) continue;
		if(!dfs(i.ss, x, c ^ i.ff)) return 0;
	}
	return 1;
}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, M; cin>>N>>M;
	for(int i=1; i<N; ++i){
		int x,y; cin>>x>>y;
		edge0[x].push_back(y), edge0[y].push_back(x);
	}
	iota(par, par+N+1, 0);
	dfs0(1, 0);
	for(int i=1; i<19; ++i) for(int j=1; j<=N; ++j) prt[i][j] = prt[i-1][prt[i-1][j]]; 
 
	for(int i=0; i<M; ++i){
		int x,y,l; cin>>x>>y;
		l = lca(x, y);
		if(l!=x && l!=y) edge[x].emplace_back(1, y), edge[y].emplace_back(1, x);
		for(int v=fnd(x); dth[prt[0][v]]>dth[l]; v=fnd(prt[0][v])){
			edge[v].emplace_back(0, prt[0][v]), edge[prt[0][v]].emplace_back(0, v);
			uni(v, prt[0][v]);
		}
		for(int v=fnd(y); dth[prt[0][v]]>dth[l]; v=fnd(prt[0][v])){
			edge[v].emplace_back(0, prt[0][v]), edge[prt[0][v]].emplace_back(0, v);
			uni(v, prt[0][v]);
		}
	}
	memset(dir, -1, sizeof(dir));
	int ans = 1;
	for(int i=2; i<=N; ++i) if(dir[i]==-1){
		if(dfs(i, 0, 0)) ans = (ans<<1)%mod;
		else return !printf("\n");
	}
	cout<<ans;
	return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 32704 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 64708 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15820 KB Output is correct
2 Incorrect 10 ms 15948 KB Output isn't correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 15748 KB Output is correct
2 Incorrect 10 ms 15888 KB Output isn't correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 16332 KB Output is correct
2 Incorrect 11 ms 16344 KB Output isn't correct

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 16332 KB Output is correct
2 Incorrect 11 ms 16284 KB Output isn't correct

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 350 ms 52844 KB Output is correct
2 Correct 419 ms 62824 KB Output is correct
3 Incorrect 193 ms 45752 KB Output isn't correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 396 ms 56976 KB Output is correct
2 Correct 419 ms 56816 KB Output is correct
3 Incorrect 325 ms 44332 KB Output isn't correct

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 402 ms 57316 KB Output is correct
2 Correct 389 ms 53676 KB Output is correct
3 Incorrect 306 ms 49684 KB Output isn't correct

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 57712 KB Output is correct
2 Correct 473 ms 65884 KB Output is correct
3 Incorrect 388 ms 46388 KB Output isn't correct