Submission #211119

#	Time	Username	Problem	Language	Result	Execution time	Memory
211119		arnold518	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	140 ms	19832 KiB

oneway

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, M, P;
pii E[MAXN+10];
vector<pii> adj[MAXN+10], adj2[MAXN+10];
int ans[MAXN+10];
char S[5]="!BRL";

int dfn[MAXN+10], low[MAXN+10], cnt;

void dfs(int now, int bef)
{
	dfn[now]=low[now]=++cnt;
	for(auto nxt : adj[now])
	{
		if(nxt.second==bef) continue;
		if(dfn[nxt.first]==0)
		{
			dfs(nxt.first, nxt.second);
			low[now]=min(low[now], low[nxt.first]);
			if(low[nxt.first]<=dfn[now]) ans[nxt.second]=1;
		}
		else
		{
			ans[nxt.second]=1;
			low[now]=min(low[now], dfn[nxt.first]);
		}
	}
}

int bcc[MAXN+10], bcnt;
void color(int now, int col)
{
	bcc[now]=col;
	for(auto nxt : adj[now])
	{
		if(bcc[nxt.first]) continue;
		if(ans[nxt.second]) color(nxt.first, col);
		else
		{
			++bcnt;
			adj2[col].push_back({bcnt, nxt.second});
			//printf("!%d %d!\n", col, bcnt);
			color(nxt.first, bcnt);
		}
	}
}

int dp[MAXN+10];
void dfs2(int now)
{
	for(auto nxt : adj2[now])
	{
		dfs2(nxt.first);
		if(dp[nxt.first]>0)
		{
			int u=E[nxt.second].first;
			if(bcc[u]==nxt.first) ans[nxt.second]=2;
			else ans[nxt.second]=3;
		}
		else if(dp[nxt.first]<0)
		{
			int u=E[nxt.second].first;
			if(bcc[u]==nxt.first) ans[nxt.second]=3;
			else ans[nxt.second]=2;
		}
		else ans[nxt.second]=1;
		dp[now]+=dp[nxt.first];
	}
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=M; i++)
	{
		scanf("%d%d", &E[i].first, &E[i].second);
		adj[E[i].first].push_back({E[i].second, i});
		adj[E[i].second].push_back({E[i].first, i});
	}

	vector<int> root;
	for(i=1; i<=N; i++)
	{
		if(dfn[i]) continue;
		dfs(i, 0);
		++bcnt; root.push_back(bcnt);
		color(i, bcnt);
	}

	scanf("%d", &P);
	while(P--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		if(bcc[u]==bcc[v]) continue;
		int bu=bcc[u], bv=bcc[v];
		dp[bu]++; dp[bv]--;
	}

	for(auto it : root) dfs2(it);

	//for(i=1; i<=N; i++) printf("%d ", bcc[i]); printf("\n");

	for(i=1; i<=M; i++) printf("%c", S[ans[i]]);
	printf("\n");
} 

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:81:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
oneway.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &E[i].first, &E[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &P);
  ~~~~~^~~~~~~~~~
oneway.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~

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