Submission #347612

#	Time	Username	Problem	Language	Result	Execution time	Memory
347612		soroush	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	98 ms	144236 KiB

oneway

/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn = 3e6;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , m , p;
vector < int > adj[maxn];
vector < pii > e;
vector < pii > query;

int par[maxn];

bool mark[maxn];
int h[maxn];
int up[maxn];

int getpar(int v){
   return((v == par[v]) ? v : par[v] = getpar(par[v]));
}

void merge(int u, int v){
   if((v = getpar(v)) == (u = getpar(u)))
      return;
   par[u] = v;
}

void dfs(int v , int p = 0){
   mark[v] = 1;
   up[v] = h[v];
   for(auto u : adj[v])
      if(!mark[u])
         h[u] = h[v] + 1,
         dfs(u , v),
         up[v] = min(up[v] , up[u]);
      else if (u!=p)
         up[v] = min(up[v] , h[u]);
   if(up[v] < h[v])
      merge(v , p);
}

int prt[maxn];

vector < int > Adj[maxn];
int H[maxn];

void DFS(int v){
	mark[v] = 1;
	for(auto u : Adj[v])
		if(!mark[u])
			H[u] = H[v] + 1, DFS(u) , prt[v] += prt[u];
}

int32_t main(){
   migmig;
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i ++){
		int u , v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
		e.pb({u , v});
	}
	cin >> p;
	for(int i = 0 ; i < p ; i ++){
		int x , y;
		cin >> x >> y;
		query.pb({x , y});
	}
	for(int i = 1 ; i <= n ; i ++)
		par[i] = i;
	for(int i = 1 ; i <= n ; i ++)
		if(!mark[i])dfs(i);
	for(int i = 0 ; i < p ; i ++){
		int u = query[i].first;
		int v = query[i].second;
		if(getpar(u) == getpar(v))continue;
		prt[getpar(u)]++ , prt[getpar(v)]--;
	}
	for(int i = 0 ; i < m ; i ++){
		int u = e[i].first;
		int v = e[i].second;
		if(getpar(u) == getpar(v))continue;
		Adj[getpar(u)].pb(getpar(v));
		Adj[getpar(v)].pb(getpar(u));
	}
	ms(mark , 0);
	for(int i = 1 ; i <= n ; i ++)
		if(!mark[getpar(i)])DFS(getpar(i));
    for(auto uv : e){
      if(getpar(uv.first) == getpar(uv.second))
         cout << "B";
		else{
			int u = getpar(uv.first) , v = getpar(uv.second);
			if(H[u] > H[v]){
				
				if(prt[u] > 0)
					cout << "R";
				else
					cout << "L";
			}
			else{
				
				if(prt[v] > 0)	
					cout << "L";
				else
					cout << "R";
			}
		  }
	}
   return(0);
}

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