제출 #163339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163339		alishahali1382	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	128 ms	18288 KiB

oneway

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
using namespace std;
typedef pair<int, int> pii;
#define pb push_back
const int MAXN = 100010;

int n, m, k, u, v, x, y, t, a, b;
int val[MAXN];
char ans[MAXN];
int E[MAXN][2];
int H[MAXN];
int comp[MAXN];
vector<pii> G[MAXN];
vector<int> G2[MAXN], bridge;

int Bridge(int node, int par, int parid){
	int res=H[node]=H[par]+1;
	for (pii p:G[node]) if (p.second!=parid){
		int v=p.first, i=p.second;
		if (H[v]){
			res=min(res, H[v]);
			ans[i]='B';
		}
		else res=min(res, Bridge(v, node, i));
	}
	if (res<H[node]){
		ans[parid]='B';
		G2[par].pb(node);
		G2[node].pb(par);
	}
	else if (parid) bridge.pb(parid);
	
	return res;
}

void dfs1(int node, int id){
	comp[node]=id;
	for (int v:G2[node]) if (!comp[v]) dfs1(v, id);
}

int dfs2(int node, int par, int parid){
	H[node]=H[par]+1;
	for (pii p:G[node]) if (p.first!=par) val[node]+=dfs2(p.first, node, p.second);
	if (val[node]==0) ans[parid]='B';
	else if (val[node]<0 ^ E[parid][0]==par) ans[parid]='L';
	else ans[parid]='R'; 
	return val[node];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<=m; i++){
		cin>>u>>v;
		E[i][0]=u, E[i][1]=v;
		G[u].pb({v, i});
		G[v].pb({u, i});
	}
	for (int i=1; i<=n; i++) if (!H[i]) Bridge(i, i, 0);
	for (int i=1; i<=n; i++) if (!comp[i]) dfs1(i, i);
	for (int i=1; i<=n; i++) G[i].clear();
	for (int i:bridge){
		E[i][0]=comp[E[i][0]];
		E[i][1]=comp[E[i][1]];
		int u=E[i][0], v=E[i][1];
		G[u].pb({v, i});
		G[v].pb({u, i});
	}
	cin>>k;
	while (k--){
		cin>>u>>v;
		u=comp[u];
		v=comp[v];
		val[u]++;
		val[v]--;
	}
	memset(H, 0, sizeof(H));
	for (int i=1; i<=n; i++) if (!H[i]) dfs2(i, i, 0);
	
	for (int i=1; i<=m; i++) cout<<ans[i]; 
	
	return 0;
}

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

oneway.cpp: In function 'int dfs2(int, int, int)':
oneway.cpp:46:20: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  else if (val[node]<0 ^ E[parid][0]==par) ans[parid]='L';
           ~~~~~~~~~^~

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