oj.uz

답안 #376545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376545 2021-03-11T16:42:38 Z SavicS Usmjeri (COCI17_usmjeri) C++14
140 / 140
 537 ms 83948 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 300005;
const int inf = 1e9 + 5;
const int mod = 1e9 + 7;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, m;

vector<int> g[maxn];

int d[maxn];
int low[maxn];
int deda[maxn][20];
void dfs1(int v, int p){
	low[v] = d[v];
	deda[v][0] = p;
	ff(i,1,19)deda[v][i] = deda[deda[v][i - 1]][i - 1];
	for(auto u : g[v]){
		if(u != p){
			d[u] = d[v] + 1;
			dfs1(u, v);
		}
	}
}
int lca(int x, int y){
	if(d[x] < d[y])swap(x, y);
	fb(i,19,0){
		if((d[x] - d[y]) & (1 << i))x = deda[x][i];
	}
	fb(i,19,0){
		if(deda[x][i] != deda[y][i]){
			x = deda[x][i];
			y = deda[y][i];
		}
	}
	return (x == y ? x : deda[x][0]);
}

vector<pii> e[maxn];

void add_edge(int x, int y, int z){
	e[x].pb({y, z});
	e[y].pb({x, z});
}

int mn[maxn];
void dfs2(int v, int p){
	mn[v] = low[v];
	for(auto u : g[v]){
		if(u != p){
			dfs2(u, v);
			if(mn[u] < d[v])add_edge(u, v, 0);
			mn[v] = min(mn[v], mn[u]);
		}
	}
}

bool bip = 0;
int boja[maxn];
bool visited[maxn];
void dfs3(int v, int clr){
	visited[v] = 1; 
	boja[v] = clr;
	for(auto c : e[v]){
		int u = c.fi;
		int w = c.se;
		if(!visited[u]){
			dfs3(u, clr ^ w);
		}
		else{
			if(boja[u] != clr ^ w)bip = 1;
		}
	}
}

int main()
{
   	ios::sync_with_stdio(false);
   	cout.tie(nullptr);
  	cin.tie(nullptr);
	cin >> n >> m;
	ff(i,1,n - 1){
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs1(1, -1);
	ff(i,1,n)low[i] = d[i];
	ff(i,1,m){
		int a, b;
		cin >> a >> b;
		int c = lca(a, b);
		low[a] = min(low[a], d[c]);
		low[b] = min(low[b], d[c]);
		if(c != a && c != b)add_edge(a, b, 1);
	}
	dfs2(1, -1);
	ll rez = 1;
	ff(i,2,n){
		if(!visited[i]){
			dfs3(i, 0);
			if(bip == 1)return cout << 0, 0;
			rez = (rez * 2) % mod;
		}	
	}
	cout << rez << endl;
	return 0;
}
/**



// probati bojenje sahovski ili slicno

**/

Compilation message

usmjeri.cpp: In function 'void dfs3(int, int)':
usmjeri.cpp:92:15: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   92 |    if(boja[u] != clr ^ w)bip = 1;
      |       ~~~~~~~~^~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14572 KB Output is correct
2 Correct 13 ms 14828 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14572 KB Output is correct
2 Correct 11 ms 14720 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 15340 KB Output is correct
2 Correct 16 ms 15232 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15340 KB Output is correct
2 Correct 13 ms 15212 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 63620 KB Output is correct
2 Correct 486 ms 65388 KB Output is correct
3 Correct 271 ms 47340 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 524 ms 67880 KB Output is correct
2 Correct 484 ms 67564 KB Output is correct
3 Correct 353 ms 51128 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 507 ms 68280 KB Output is correct
2 Correct 510 ms 64492 KB Output is correct
3 Correct 345 ms 51056 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 68844 KB Output is correct
2 Correct 490 ms 69116 KB Output is correct
3 Correct 360 ms 47980 KB Output is correct