Submission #57223

#	Time	Username	Problem	Language	Result	Execution time	Memory
57223		mraron	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	822 ms	79040 KiB

oneway

/*
ID: noszaly1
TASK: {TASK}
LANG: C++11               
*/

//Noszály Áron 10o Debreceni Fazekas Mihály Gimnázium

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=acos(-1);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

struct el {
	int xx;
	bool yy;
	int ind;
};

int n,m;
vector<el> adj[100001], cadj[100001];

int b1[100001];
int dfs_ind=0, cind=0, comp[100001];
int dfs_num[100001], dfs_low[100001], par[100001];
map<pair<int,int>, bool> bridge; 


void dfs1(int x) {
	dfs_num[x]=dfs_low[x]=++dfs_ind;
	b1[x]=1;
	
	for(auto i:adj[x]) {
		if(par[x]==i.ind) continue ;
		if(!b1[i.xx]) {
			par[i.xx]=i.ind;
			dfs1(i.xx);
			
			if(dfs_low[x]>dfs_low[i.xx]) {
				dfs_low[x]=dfs_low[i.xx];
			}
			
			if(dfs_low[i.xx]==dfs_num[i.xx]) {
			//	cerr<<x<<" "<<i.xx<<"\n";
				bridge[{x, i.xx}]=true;
				bridge[{i.xx, x}]=true;
			}
		}else {
			if(dfs_low[x]>dfs_num[i.xx]) {
				dfs_low[x]=dfs_num[i.xx];
			}
		}
	}
	//cerr<<x<<" "<<dfs_num[x]<<" "<<dfs_low[x]<<"\n";
	b1[x]=2;
}

int b15[100001];

void dfs15(int x) {
	b15[x]=1;
	comp[x]=cind;
	for(auto i:adj[x]) {
		if(b15[i.xx]) continue ;
		if(bridge[mp(x, i.xx)]) continue ;
		dfs15(i.xx);
	}
	b15[x]=2;
}

int dp[100001][17], b2[100001], lvl[100001];

int up[100001][17];
int down[100001][17];

el parel[100001];

void dfs2(int x) {
	b2[x]=1;
	for(auto i:cadj[x]) {
		if(!b2[i.xx]) {
			dp[i.xx][0]=x;
			lvl[i.xx]=lvl[x]+1;
			parel[i.xx]=i;
			dfs2(i.xx);
		}
	}
	b2[x]=1;
}

void calc() {
	for(int j=1;j<17;++j) {
		for(int i=1;i<=cind;++i) {
			if(dp[i][j-1]>0) {
				dp[i][j]=dp[dp[i][j-1]][j-1];
			}
		}
	}
}

int lca(int p, int q) {
	if(lvl[p]<lvl[q]) swap(p,q);
	int i;
	for(i=16;i>=0;i--) {
		if(dp[p][i]>0 && lvl[p]-lvl[q]>=(1<<i)) {
			p=dp[p][i];
		}
	}
	if(p==q) return p;
	
	for(i=16;i>=0;i--) {
		if(dp[p][i]>0 && dp[p][i]!=dp[q][i]) {
			p=dp[p][i];
			q=dp[q][i];
		}
	}
	
	return dp[p][0];
}

void setUp(int p, int v) {
	if(lvl[v]-lvl[p]==0) return ;
	for(int i=16;i>=0;i--) {
		if(lvl[v]-lvl[p]>=(1<<i)) {
			up[v][i]=1;
			v=dp[v][i];
		}
	}
}

void setDown(int p, int v) {
	if(lvl[v]-lvl[p]==0) return ;
	for(int i=16;i>=0;i--) {
		if(lvl[v]-lvl[p]>=(1<<i)) {
			down[v][i]=1;
			v=dp[v][i];
		}
	}
}




int main() {
	IO;
	
	cin>>n>>m;

	for(int i=0;i<m;++i) {
		int a,b;
		cin>>a>>b;
		adj[a].pb({b,false,i});
		adj[b].pb({a,true,i});
		
	}

	for(int i=1;i<=n;++i) {
		if(!b1[i]) dfs1(i);
	}
	
	for(int i=1;i<=n;++i) {
		if(!b15[i]) {
			cind++;
			dfs15(i);
		}
	}
	
//	for(int i=1;i<=n;++i) cerr<<comp[i]<<" ";
//	cerr<<"\n";
	
	for(int i=1;i<=n;++i) {
		for(auto j:adj[i]) {
			if(comp[i]!=comp[j.xx]) {
				cadj[comp[i]].pb({comp[j.xx], j.yy, j.ind});
			}
		}
	}
	
	for(int i=1;i<=cind;++i) {
		if(!b2[i]) dfs2(i);
	}

	calc();

	int q;
	cin>>q;
	vector<pair<int,int>> qs(q);
	
	vector<int> ans(m);
	for(int i=0;i<q;++i) {
		int a,b;
		cin>>a>>b;
		
		qs[i]={a,b};
		
		if(comp[a]!=comp[b]) {
			int l=lca(comp[a],comp[b]);
	//		cerr<<l<<" "<<comp[a]<<"up\n";
			setUp(l, comp[a]);
		//	cerr<<l<<" "<<comp[b]<<"down\n";
			setDown(l, comp[b]);
		}
	}
	
	for(int j=16;j>0;j--) {
		for(int i=1;i<=cind;++i) {
			if(up[i][j]) {
				up[i][j-1]=1;
				up[dp[i][j-1]][j-1]=1;
			}
			
			if(down[i][j]) {
				down[i][j-1]=1;
				down[dp[i][j-1]][j-1]=1;
			}
		}
	}

	for(int i=1;i<=cind;++i) {
		if(parel[i].xx==0) continue ;
		if(up[parel[i].xx][0]) {
			if(parel[i].yy) ans[parel[i].ind]=2;
			else ans[parel[i].ind]=1;
		}
		
		if(down[parel[i].xx][0]) {
			if(parel[i].yy) ans[parel[i].ind]=1;
			else ans[parel[i].ind]=2;
		}
	}
	
	for(int i=0;i<m;++i) {
		cout<<"BLR"[ans[i]];
	}cout<<"\n";

	return 0;
}

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