oj.uz

Submission #211114

# Submission time Handle Problem Language Result Execution time Memory
211114 2020-03-19T08:54:24 Z arnold518 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 8 ms 4992 KB 
#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;
			color(nxt.first, bcnt);
			adj2[col].push_back({bcnt, nxt.second});
		}
	}
}

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<=M; i++) printf("%c", S[ans[i]]);
	printf("\n");
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:80:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
oneway.cpp:82: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:85: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:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &P);
  ~~~~~^~~~~~~~~~
oneway.cpp:103: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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -