oj.uz

Submission #226808

# Submission time Handle Problem Language Result Execution time Memory
226808 2020-04-25T13:45:35 Z stefdasca One-Way Streets (CEOI17_oneway) C++14
0 / 100
 8 ms 5248 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

// #define fisier 1

using namespace std;

typedef long long ll;

const int mod = 1000000007;
const double dancila = 3.14159265359; // PI 
const double eps = 1e-9;


int n, m, lvl[100002], low[100002], viz[100002];
vector<pair<int, int> > v[100002], v2[100002];

pair<int, int> E[100002];
int ans[100002];
void dfs(int dad, int nod)
{
	viz[nod] = 1;
	lvl[nod] = lvl[dad] + 1;
	low[nod] = lvl[nod];
	for(auto vecin : v[nod])
	{
		if(vecin.fi == dad)
			continue;
		if(viz[vecin.fi])
		{
			low[nod] = min(low[nod], lvl[vecin.fi]);
			ans[vecin.se] = 1;
			continue;
		}
		dfs(nod, vecin.fi);
		if(low[vecin.fi] <= lvl[nod])
			ans[vecin.se] = 1;
		low[nod] = min(low[nod], low[vecin.fi]);
	}
}

int bcc[100002], bcnt;
void dfs2(int nod, int col)
{
	bcc[nod] = col;
	for(auto vecin : v[nod])
	{
		if(bcc[vecin.fi]) 
			continue;
		if(ans[vecin.se]) 
			dfs2(vecin.fi, col);
		else
		{
			++bcnt;
			v2[col].push_back({bcnt, vecin.se});
			dfs2(vecin.fi, bcnt);
		}
	}
}

int dp[100002];
void dfs3(int nod)
{
	for(auto vecin : v2[nod])
	{
		dfs3(vecin.fi);
		if(dp[vecin.fi]>0)
		{
			int u=E[vecin.se].fi;
			if(bcc[u]==vecin.fi) 
				ans[vecin.se]=2;
			else 
				ans[vecin.se]=3;
		}
		else 
			if(dp[vecin.fi]<0)
			{
				int u=E[vecin.se].fi;
				if(bcc[u]==vecin.fi) 
					ans[vecin.se]=3;
				else 
					ans[vecin.se]=2;
			}
			else 
				ans[vecin.se]=1;
		dp[nod]+=dp[vecin.fi];
	}
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	cin >> n >> m;
	for(int i = 1; i <= m; ++i)
	{
	    int a, b;
	    cin >> a >> b;
	    E[i] = {a, b};
	    v[a].pb({b, i});
	    v[b].pb({a, i});
	}
	
	vector<int> rad;
	for(int i = 1; i <= n; ++i)
		if(!viz[i])
		{
			dfs(0, i);
			++bcnt;
			rad.pb(bcnt);
			dfs2(i, bcnt);
		}
	
	int p;
	cin >> p;
	for(; p; --p)
	{
		int a, b;
		cin >> a >> b;
		if(bcc[a] == bcc[b])
			continue;
		++dp[bcc[a]];
		--dp[bcc[b]];
	}
	
	for(auto it : rad) 
		dfs3(it);
	char ch[5] = "XBRL";
	for(int i = 1; i <= m; ++i)
		cout << ch[ans[i]];
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 5152 KB Output is correct
9 Incorrect 7 ms 5120 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 5152 KB Output is correct
9 Incorrect 7 ms 5120 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 5152 KB Output is correct
9 Incorrect 7 ms 5120 KB Output isn't correct
10 Halted 0 ms 0 KB -