Submission #237341

#	Time	Username	Problem	Language	Result	Execution time	Memory
237341		nikatamliani	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	8 ms	2688 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, LG = 20;
int d[N], a[N], b[N], in[N], out[N], dp[N], p[N][2], L[N][LG], n, m, q;
vector < int > edges[N];
bool ok[N], vis[N], marked[N][2];
map < pair < int, int >, int > ind;
void dfs(int x, int p){
	static int timer = 0;
	vis[x] = true; 
	d[x] = d[p] + 1;
	L[x][0] = p;
	for(int i = 1; i < LG; ++i) L[x][i] = L[L[x][i - 1]][i - 1];
	in[x] = ++timer;
	for(int i = 0; i < (int)edges[x].size(); ++i){
		int to = edges[x][i];
		if(to != p){
			if(!vis[to]){
				dfs(to, x);
				dp[x] += dp[to];
			}else{
				dp[x] += in[x] < in[to] ? -1 : 1;
			}
		}
	}
	out[x] = ++timer;
	ok[ind[{x, p}]] = !dp[x];
}
bool isAnc(int potAnc, int potChild){
	return !potAnc || in[potAnc] <= in[potChild] && out[potAnc] >= out[potChild];
}
int lca(int u, int v){
	if(isAnc(u, v))return u;
	if(isAnc(v, u))return v;
	for(int i = LG - 1; ~i; --i){
		if(!isAnc(L[u][i], v))u = L[u][i];
	}
	return L[u][0];
}
int find(int x, int dist){
	for(int bit = 0; bit < LG; ++bit){
		if(dist >> bit & 1)x = L[x][bit];
	}
	return x;
}
void make_set(int x){
	p[x][0] = p[x][1] = x;
	marked[x][0] = marked[x][1] = 0;
}
int find_set(int x, bool TYPE){
	return p[x][TYPE] == x ? x : p[x][TYPE] = find_set(p[x][TYPE], TYPE);
}
void union_sets(int a, int b, bool TYPE){
	a = find_set(a, TYPE);
	b = find_set(b, TYPE);
	marked[a][TYPE] = marked[b][TYPE] = 1;
	if(a == b)return;
	if(d[a] > d[b])swap(a, b);
	p[b][TYPE] = a;
}
void unite(int fr, int to, bool TYPE){
	while(d[fr] >= d[to]){
		int nxt = L[find_set(fr, TYPE)][0];
		union_sets(fr, to, TYPE);
		fr = nxt;
	}
}
void directEdges(int fr, int to){
	int l = lca(fr, to);
	int dist1 = d[fr] - d[l];
	int dist2 = d[to] - d[l];
	if(dist1)unite(fr, find(fr, dist1 - 1), 0);
	if(dist2)unite(to, find(to, dist2 - 1), 1);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int u, v, i = 1; i <= m; ++i){
		cin >> a[i] >> b[i];
		edges[a[i]].push_back(b[i]);
		edges[b[i]].push_back(a[i]);
		ind[{a[i], b[i]}] = ind[{b[i], a[i]}] = i;
	}
	for(int i = 1; i <= n; ++i)make_set(i);
	dfs(1, 0);
	cin >> q;
	for(int u, v, i = 1; i <= q; ++i){
		cin >> u >> v;
		directEdges(u, v);
	}
	for(int i = 1; i <= m; ++i){
		char direction = 'B';
		if(ok[i]){
			int child = a[i], parent = b[i];
			bool swapped = false;
			if(d[child] < d[parent])swap(parent, child), swapped = true;
			int x = find_set(child, 0);
			int y = find_set(child, 1);
			if(marked[x][0]) direction = 'R';
			if(marked[y][1]) direction = 'L';
			if(swapped)direction = 'L' + 'R' - direction;
		}
		cout << direction;
	}
}

Compilation message (stderr)

oneway.cpp: In function 'bool isAnc(int, int)':
oneway.cpp:30:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  return !potAnc || in[potAnc] <= in[potChild] && out[potAnc] >= out[potChild];
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:79:10: warning: unused variable 'u' [-Wunused-variable]
  for(int u, v, i = 1; i <= m; ++i){
          ^
oneway.cpp:79:13: warning: unused variable 'v' [-Wunused-variable]
  for(int u, v, i = 1; i <= m; ++i){
             ^

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40