oj.uz

Submission #57223

# Submission time Handle Problem Language Result Execution time Memory
57223 2018-07-14T09:50:32 Z mraron One-Way Streets (CEOI17_oneway) C++14
100 / 100
 822 ms 79040 KB 
/*
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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5416 KB Output is correct
4 Correct 9 ms 5784 KB Output is correct
5 Correct 13 ms 5936 KB Output is correct
6 Correct 8 ms 5936 KB Output is correct
7 Correct 11 ms 6004 KB Output is correct
8 Correct 9 ms 6016 KB Output is correct
9 Correct 7 ms 6016 KB Output is correct
10 Correct 7 ms 6016 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5416 KB Output is correct
4 Correct 9 ms 5784 KB Output is correct
5 Correct 13 ms 5936 KB Output is correct
6 Correct 8 ms 5936 KB Output is correct
7 Correct 11 ms 6004 KB Output is correct
8 Correct 9 ms 6016 KB Output is correct
9 Correct 7 ms 6016 KB Output is correct
10 Correct 7 ms 6016 KB Output is correct
11 Correct 93 ms 13784 KB Output is correct
12 Correct 113 ms 16860 KB Output is correct
13 Correct 182 ms 21044 KB Output is correct
14 Correct 235 ms 28548 KB Output is correct
15 Correct 295 ms 31996 KB Output is correct
16 Correct 459 ms 45032 KB Output is correct
17 Correct 423 ms 60800 KB Output is correct
18 Correct 470 ms 60800 KB Output is correct
19 Correct 442 ms 63064 KB Output is correct
20 Correct 103 ms 63064 KB Output is correct
21 Correct 100 ms 63064 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5416 KB Output is correct
4 Correct 9 ms 5784 KB Output is correct
5 Correct 13 ms 5936 KB Output is correct
6 Correct 8 ms 5936 KB Output is correct
7 Correct 11 ms 6004 KB Output is correct
8 Correct 9 ms 6016 KB Output is correct
9 Correct 7 ms 6016 KB Output is correct
10 Correct 7 ms 6016 KB Output is correct
11 Correct 93 ms 13784 KB Output is correct
12 Correct 113 ms 16860 KB Output is correct
13 Correct 182 ms 21044 KB Output is correct
14 Correct 235 ms 28548 KB Output is correct
15 Correct 295 ms 31996 KB Output is correct
16 Correct 459 ms 45032 KB Output is correct
17 Correct 423 ms 60800 KB Output is correct
18 Correct 470 ms 60800 KB Output is correct
19 Correct 442 ms 63064 KB Output is correct
20 Correct 103 ms 63064 KB Output is correct
21 Correct 100 ms 63064 KB Output is correct
22 Correct 822 ms 68420 KB Output is correct
23 Correct 616 ms 68896 KB Output is correct
24 Correct 570 ms 71440 KB Output is correct
25 Correct 576 ms 79040 KB Output is correct
26 Correct 716 ms 79040 KB Output is correct
27 Correct 613 ms 79040 KB Output is correct
28 Correct 60 ms 79040 KB Output is correct
29 Correct 138 ms 79040 KB Output is correct
30 Correct 240 ms 79040 KB Output is correct
31 Correct 189 ms 79040 KB Output is correct
32 Correct 286 ms 79040 KB Output is correct