Submission #71872

#	Time	Username	Problem	Language	Result	Execution time	Memory
71872		bnahmad15	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	579 ms	59692 KiB

oneway

#include <bits/stdc++.h>
#define forn(i,j,n) for(int i = (int)j;i<=(int)n;i++)
#define nfor(i,j,n) for(int i = (int)j;i>=(int)n;i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 100001,LOG = 17;

int n,m,p,u,v,x[N],y[N],is[N],cnt = 0,num[N],low[N],det[N],cc = 0,comp[N],vis[N],nxt[N],pr[N][LOG],dep[N];
pair<int,int> st[N];
vector<pair<int,pii> > g[N],g2[N];
map <pii,int> mp;
char res[N];

inline pii rev(pii a){
	if(a.second == 1)
		a.second = 2;
	else if(a.second == 2)
		a.second = 1;
	return a;
}
void dfs(int uu,int prnt){
	low[uu] = num[uu] = ++cnt;
	forn(i,0,g[uu].size()-1){
		int vv = g[uu][i].first;
		if(num[vv] == -1){
			dfs(vv,uu);
			if(low[vv] > num[uu]){
				is[g[uu][i].second.first] = 1;
			}
			low[uu] = min(low[uu],low[vv]);
		}else if(vv != prnt){
			low[uu] = min(low[uu],num[vv]);
		}
	}
}

void DFS(int node,int numb){
	if(vis[node] == 1)
		return;
	vis[node] = 1;
	comp[node] = numb;
	forn(i,0,g[node].size()-1){
		int to = g[node][i].first;
		if(vis[to])
			continue;
		if(is[g[node][i].second.first] == 1){
			continue;
		}else{
			DFS(to,numb);
		}
	}
}

void dfs2(int node,int prnt,int depth,pii state){
	pr[node][0] = prnt;
	dep[node] = depth;
	st[node] = rev(state);
	forn(i,0,g2[node].size()-1){
		if(g2[node][i].first == prnt)
			continue;
		dfs2(g2[node][i].first,node,depth+1,g2[node][i].second);
	}
}
int LCA(int a,int b){
	if(dep[a] < dep[b])
		swap(a,b);
	nfor(i,LOG-1,0){
		if(dep[a] - (1<<i) >= dep[b])
			a = pr[a][i];
	}
	if(a == b)
		return a;
	nfor(i,LOG-1,0){
		if(pr[a][i] != pr[b][i]){
			a = pr[a][i];
			b = pr[b][i];
		}
	}
	return pr[a][0];
}
int FIND(int a){return ((nxt[a] == a) ? a : nxt[a] = FIND(nxt[a]));}
void UNION(int a,int b){
	int fa = FIND(a);
	int fb = FIND(b);
	nxt[fa] = fb;
}
void calc(int a,int b,int dir){
	if(dep[a] <= dep[b])
		return;
	int fa = FIND(a);
	if(a == fa){
		if(dir == 1)
			det[st[a].first] = st[a].second;
		else{
			pii tmp = rev(st[a]);
			det[tmp.first] = tmp.second;
		}
		UNION(a,FIND(pr[a][0]));
		calc(pr[a][0],b,dir);
	}else{
		calc(fa,b,dir);
	}
}
int main(){

	scanf("%d%d",&n,&m);
	forn(i,1,m){
		scanf("%d%d",&u,&v);
		g[u].push_back(make_pair(v,make_pair(i,1)));
		g[v].push_back(make_pair(u,make_pair(i,2)));
		if(u > v)
			swap(u,v);
		mp[make_pair(u,v)]++;
		is[i] = 0;
	}
	scanf("%d",&p);
	forn(i,1,p){
		scanf("%d%d",&x[i],&y[i]);
	}
	forn(i,1,n){
		num[i] = low[i] = -1;
		vis[i] = 0;
	}
	forn(i,1,n){
		if(num[i] == -1)
			dfs(i,0);
	}
	forn(i,1,n){
		forn(j,0,g[i].size()-1){
			u = i,v = g[i][j].first;
			if(u > v)
				swap(u,v);
			if(mp[make_pair(u,v)] > 1)
				is[g[i][j].second.first] = 0;
			if(u == v)
				is[g[i][j].second.first] = 0;
		}
	}
	forn(i,1,n){
		dep[i] = -1;
		if(vis[i] == true)
			continue;
		DFS(i,++cc);
	}
	forn(i,1,n){
		forn(j,0,g[i].size()-1){
			u = i,v = g[i][j].first;
			if(comp[u] == comp[v])
				continue;
			g2[comp[u]].push_back(make_pair(comp[v],g[i][j].second));
		}
		nxt[i] = i;
	}
	forn(i,1,m){
		det[i] = 0;
		if(is[i] == 1)
			continue;
		res[i] = 'B';
	}
	forn(i,1,cc){
		if(dep[i] != -1)
			continue;

		dfs2(i,0,0,make_pair(0,0));
	}
	forn(i,1,LOG-1){
		forn(j,1,cc){
			pr[j][i] = pr[pr[j][i-1]][i-1];
		}
	}
	forn(i,1,p){
		if(comp[x[i]] == comp[y[i]])
			continue;
		int C = LCA(comp[x[i]],comp[y[i]]);
		calc(comp[x[i]],C,1);
		calc(comp[y[i]],C,2);
	}
	forn(i,1,m){
		if(is[i] == 0)
			continue;
		if(det[i] == 1)
			res[i] = 'R';
		else if(det[i] == 2)
			res[i] = 'L';
		else
			res[i] = 'B';
	}
	forn(i,1,m)
		printf("%c",res[i]);
	return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:107: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:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~
oneway.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&p);
  ~~~~~^~~~~~~~~
oneway.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

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