제출 #44554

#제출 시각아이디문제언어결과실행 시간메모리
44554MatheusLealVOne-Way Streets (CEOI17_oneway)C++17
100 / 100
404 ms34992 KiB
#include <bits/stdc++.h>
#define N 100050
#define logn 20
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
 
int q, n, m, dfsnum[N], dfslow[N], cnt, pai[N];
 
int dp[N], ans[N];
 
int solved[N];
 
vector<int> pontes;
 
map<pii, int> ccnt;
 
vector<pii> G[N], A, grafo[N];
 
void dfs(int x)
{
	dfsnum[x] = dfslow[x] = ++cnt;
 
	for(int i = 0; i< G[x].size(); i++)
	{
		int v = G[x][i].f, id = G[x][i].s;
 
		if(!dfsnum[v])
		{
			pai[v] = x;
 
			dfs(v);
 
			if(dfslow[v] > dfsnum[x] && ccnt[{ min(x, v), max(x, v) }] == 1 ) pontes.push_back(id);
 
			dfslow[x] = min(dfslow[v], dfslow[x]);
		}
 
		else if(v != pai[x]) dfslow[x] = min(dfsnum[v], dfslow[x]);
	}
}
 
int ok[N], esq[N], dir[N];
 
vector<pii> tree[N];
 
void get_tree(int x)
{
	ok[x] = 1;
 
	for(auto v: G[x])
	{
		if(ok[v.f]) continue;
		
		tree[x].push_back(v);
 
		tree[v.f].push_back({x, v.s});
 
		get_tree(v.f);
	}
}
 
int solve(int x, int p)
{
	for(auto v: tree[x])
	{
		if(v.f == p) continue;
		
		int child = solve(v.f, x);
 
		bool brg = binary_search(pontes.begin(), pontes.end(), v.s);
 
		if(child > 0 && brg)
		{
			if(esq[v.s] == x) ans[v.s] = -1;
 
			else ans[v.s] = 1;
		}
 
		else if(child < 0 && brg)
		{
			if(esq[v.s] == x) ans[v.s] = 1;
 
			else ans[v.s] = -1;
		}
 
		dp[x] += child;
	}
 
	solved[x] = 1;
 
	return dp[x];
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n>>m;
 
	for(int i = 1, a, b ;i <= m; i++)
	{
		cin>>a>>b;
 
		G[a].push_back({b, i - 1});
 
		G[b].push_back({a, i - 1});
 
		A.push_back({a, b});
 
		esq[i - 1] = a, dir[i - 1] = b;
 
		ccnt[ {min(a, b), max(a, b)}] ++;
	}
 
	for(int i = 1; i <= n; i++) if(!dfsnum[i]) dfs(i);
 
	for(auto id: pontes) grafo[ A[id].f ].push_back( {A[id].s, id} ), grafo[ A[id].s ].push_back( {A[id].f, id} );
 
	cin>>q;
 
	for(int i = 1, a, b; i <= q; i++)
	{
		cin>>a>>b;
 
		dp[a] ++, dp[b] --;
	}
 
	sort(pontes.begin(), pontes.end());
 
	for(int i = 1; i <= n; i++) if(ok[i] == 0) get_tree(i);
 
	for(int i = 1; i <= n; i++) if(!solved[i]) solve(i, i);
 
	for(int i = 0; i < m; i++)
	{
		if(ans[i] == 0) cout<<"B";
 
		else if(ans[i] > 0) cout<<"R";
 
		else cout<<"L";
	}
 
	cout<<"\n";
}

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

oneway.cpp: In function 'void dfs(int)':
oneway.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i< G[x].size(); i++)
                 ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...