Submission #125432

#	Time	Username	Problem	Language	Result	Execution time	Memory
125432		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;
	for(pair<int,int> cur : g[u]){
		int v = cur.first;
		e = cur.second;
		if(lvl[v] == 0){//span edge
			lvl[v] = lvl[u] + 1;
			findbridges(v,u,e);
			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;	
	}
}

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;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&u[i],&v[i]);
		g[u[i]].push_back({v[i],i});
		g[v[i]].push_back({u[i],i});
	}
	findbridges(1);
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			cmp++;
			getscc(i);
		}
	}
	for(int i=0;i<m;i++){
		int x = u[i],y = v[i];
		if(gid[x] == gid[y])ans[i] = 'B';
		else{
			l[gid[x]].push_back({gid[y],i});
			l[gid[y]].push_back({gid[x],i});
		}
	}
	d[1] = 1;
	calc(gid[1],0);
	int q;
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a = gid[a];
		b = gid[b];
		int c = lca(a,b);
		while(a != c){
			if(to[a] != -1){
				a = to[a];
				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];
				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:44: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:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<l[u].size();i++){
              ~^~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
oneway.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u[i],&v[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
oneway.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

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