Submission #125439

#	Time	Username	Problem	Language	Result	Execution time	Memory
125439		figter001	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	6 ms	5496 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

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

const int nax = 1e5+100;

int idx[nax],low[nax],T,gid[nax],cmp,d[nax],to[nax];
int par[nax][22],be[nax];
vector<pair<int,int>> l[nax],g[nax];
vector<int> s;
bool vis[nax],isbridge[nax];
int u[nax],v[nax];
char ans[nax];
int lvl[nax],dp[nax];

void findbridges(int u,int p = 0,int e = 0){
	dp[u] = 0;
	// cout << u << ' ' << p << endl;
	for(pair<int,int> cur : g[u]){
		int v = cur.first;
		int w = cur.second;
		if(lvl[v] == 0){//span edge
			lvl[v] = lvl[u] + 1;
			findbridges(v,u,w);
			dp[u] += dp[v];
		}else if(lvl[v] > lvl[u]){//edges downwards
			dp[u]--;
		}else if(lvl[v] < lvl[u]){//edges upwards
			dp[u]++;
		}
	}
	dp[u]--; // We dont count the edge from p to u 
	if(lvl[u] > 1 && dp[u] == 0){//edge between u and its parent is a bridge
		isbridge[e] = 1;	
		// cout << u << ' ' << p << ' ' << e << endl;
	}
}

void getscc(int u){
	vis[u]=1;
	gid[u] = cmp;
	for(int i=0;i<g[u].size();i++){
		int v = g[u][i].first;
		int e = g[u][i].second;
		if(isbridge[e])continue;
		if(!vis[v])getscc(v);
	}
}

void calc(int u,int p){
	for(int i=0;i<l[u].size();i++){
		int v = l[u][i].first;
		int id = l[u][i].second;
		if(v == p)continue;
		d[v] = d[u] + 1;
		par[v][0] = u;
		be[v] = id;
		for(int j=1;j<20;j++)
			par[v][j] = par[par[v][j-1]][j-1];
		calc(v,u);
	}
}

int lca(int u,int v){
	if(d[u] > d[v])swap(u,v);
	int dif = d[v] - d[u];
	assert(dif >=0);
	for(int k=20;k>=0;k--){
		if((dif >> k) & 1){
			v = par[v][k];
		}
	}
	if(v == u)return u;
	for(int k=20;k>=0;k--){
		if(par[u][k] != par[v][k]){
			u = par[u][k];
			v = par[v][k];
		}
	}
	return par[u][0];
}

int main(){
	memset(to,-1,sizeof(to));
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		ans[i] = 'B';
		cin>>u[i]>>v[i];
		g[u[i]].push_back({v[i],i});
		g[v[i]].push_back({u[i],i});
	}
	lvl[1] = 1;
	findbridges(1);
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			cmp++;
			// cout << i << ' ' << cmp << endl;
			getscc(i);
		}
	}
	for(int i=0;i<m;i++){
		int x = gid[u[i]],y = gid[v[i]];
		if(x != y){
			l[x].push_back({y,i});
			l[y].push_back({x,i});
		}
	}
	d[1] = 1;
	calc(1,0);
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int a,b;
		cin>>a>>b;
		a = gid[a];
		b = gid[b];
		int c = lca(a,b);
		// cout << a << ' ' << b << ' ' << lca << endl;
		while(a != c){
			// if(to[a] != -1){
			// 	a = to[a];
			// 	if(d[to[a]] > d[c])
			// 		to[a] = c;
			// 	continue;
			// }
			to[a] = c;
			int p = par[a][0];
			int x = u[be[a]],y = v[be[a]];
			x = gid[x];
			y = gid[y];
			// cout << x << ' ' << y << endl;
			if(x == a && y== p)ans[be[a]] = 'R';
			else ans[be[a]] = 'L';
			a = p;
		}
		while(b != c){
			// if(to[b] != -1){
			// 	b = to[b];
			// 	if(d[to[b]] > d[c])
			// 		to[b] = c;
			// 	continue;
			// }
			to[b] = c;
			int p = par[b][0];
			int x = u[be[b]],y = v[be[b]];
			x = gid[x];
			y = gid[y];
			if(x == b && y== p)ans[be[b]] = 'L';
			else ans[be[b]] = 'R';
			b = p;
		}
	}
	for(int i=0;i<m;i++){
		if(!ans[i])ans[i] = 'B';
		cout << ans[i];
	}
	printf("\n");
}

Compilation message (stderr)

oneway.cpp: In function 'void getscc(int)':
oneway.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++){
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void calc(int, int)':
oneway.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<l[u].size();i++){
              ~^~~~~~~~~~~~

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