제출 #711245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711245		WonderfulWhale	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	153 ms	44328 KiB

oneway

#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

const int MAXN = 100009;
const int LOG = 17;

int n, m;
int jump[MAXN];
bool bridge[MAXN];
int dep[MAXN];
vector<pii> G[MAXN];
vector<pii> G2[MAXN];
int S[MAXN];
int E[MAXN];
pii edge[MAXN];
int ans[MAXN];
bool vis[MAXN];
int tab[MAXN];
int cnt;
int T, tin[MAXN], tout[MAXN], jp2[MAXN][LOG];

void dfs1(int x, int d, int pre) {
	vis[x] = true;
	dep[x] = d;
	jump[x] = d;
	for(auto [z, id]:G[x]) {
		if(id==pre) continue;
		if(!vis[z]) {
			dfs1(z, d+1, id);
			jump[x] = min(jump[x], jump[z]);
		} else {
			jump[x] = min(jump[x], dep[z]);
		}
	}
	if(pre==-1) return;
	if(jump[x] == d) bridge[pre] = true;
	//cout << "teraz: " << x << " skok: " << jump[x] << "\n";
	//cout << pre << " " << bridge[pre] << "\n";
}

void dfs2(int x, int col) {
	vis[x] = true;
	tab[x] = col;
	for(auto [z, id]:G[x]) {
		if(!bridge[id]) {
			if(!vis[z]) dfs2(z, col);
		} else {
			if(vis[z]) {
				G2[col].pb({tab[z], id});
			} else {
				dfs2(z, ++cnt);
				G2[col].pb({tab[z], id});
			}
		}
	}
}

void dfs3(int x, int y) {
	//cout << "licze: " << x << " " << y << "\n";
	vis[x] = true;
	tin[x] = ++T;
	jp2[x][0] = y;
	for(int i=1;i<LOG;i++) {
		jp2[x][i] = jp2[jp2[x][i-1]][i-1];
	}
	for(auto [z, id]:G2[x]) {
		if(z!=y) dfs3(z, x);
	}
	tout[x] = ++T;
}

bool is_ancestor(int x, int y) {
	return tin[x]<=tin[y]&&tout[x]>=tout[y];
}

int lca(int x, int y) {
	if(is_ancestor(x, y)) return x;
	if(is_ancestor(y, x)) return y;
	for(int i=LOG-1;i>=0;i--) {
		if(!is_ancestor(jp2[x][i], y)) {
			x = jp2[x][i];
		}
	}
	return jp2[x][0];
}

pii dfs4(int x, int pre) {
	vis[x] = true;
	pii val = {0, 0};
	for(auto [z, id]:G2[x]) {
		if(id==pre) continue;
		pii nval = dfs4(z, id);
		val.st += nval.st;
		val.nd += nval.nd;
	}
	val.st += S[x];
	val.nd += E[x];
	//cout << "v: " << x << " " << val.st << " " << val.nd << "\n";
	assert(!val.st||!val.nd);
	if(pre==-1) return val;
	if(val.st) {
		//cout << "tu: " << x << " "<< tab[edge[pre].st] << "\n";
		if(x == tab[edge[pre].st]) {
			//cout << "set: " << pre << " 1\n";
			ans[pre] = -1;
		} else {
			//cout << "set: " << pre << " 2\n";
			ans[pre] = 1;
		}
	} else if(val.nd) {
		//cout << "tu\n";
		if(x == tab[edge[pre].st]) {
			//cout << "set: " << pre << " 3\n";
			ans[pre] = 1;
		} else {
			//cout << "set: " << pre << " 4\n";
			ans[pre] = -1;
		}
	}
	return val;
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb({b, i});
		G[b].pb({a, i});
		edge[i] = {a, b};
	}
	for(int i=1;i<=n;i++) {
		if(!vis[i]) {
			dfs1(i, 0, -1);
		}
	}
	memset(vis, 0, sizeof(vis));
	for(int i=1;i<=n;i++) {
		if(!vis[i]) {
			dfs2(i, ++cnt);
		}
	}
	for(int i=1;i<=n;i++) {
		//cout << i << ": " << tab[i] << "\n";
	}
	//cout << "graf\n";
	for(int i=1;i<=cnt;i++) {
		//cout << i << ":\n";
		for(pii x:G2[i]) {
			//cout << x.st << " " << x.nd << "\n";
		}
	}
	//cout << "koniec\n";
	memset(vis, 0, sizeof(vis));
	for(int i=1;i<=cnt;i++) {
		if(!vis[i]) {
			dfs3(i, 0);
		}
	}
	tin[0] = 0;
	tout[0] = ++T;
	int q;
	cin >> q;
	while(q--) {
		int a, b;
		cin >> a >> b;
		S[tab[a]]++;
		E[tab[b]]++;
		int Lca = lca(tab[a], tab[b]);
		//cout << tab[a] << " " << tab[b] << " " << Lca << " lca\n";
		S[Lca]--;
		E[Lca]--;
	}
	for(int i=1;i<=cnt;i++) {
		//cout << i << ": "<< S[i] << " " << E[i] << "\n";
	}
	memset(vis, 0, sizeof(vis));
	for(int i=1;i<=cnt;i++) {
		if(!vis[i]) {
			dfs4(i, -1);
		}
	}
	for(int i=0;i<m;i++) {
		if(ans[i]==0) {
			cout << "B";
		} else if(ans[i]==1) {
			cout << "L";
		} else {
			cout << "R";
		}
	}
	cout << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'int32_t main()':
oneway.cpp:160:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  160 |   for(pii x:G2[i]) {
      |           ^

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