Submission #238353

#	Time	Username	Problem	Language	Result	Execution time	Memory
238353		eohomegrownapps	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	449 ms	47268 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

vector<multiset<pair<int,int>>> adjlist; //node, ind or -ind if bridge
vector<int> depth;
vector<int> low; //closest to root

vector<pair<int,pair<int,int>>> bridgeedges; //ind, {n1,n2}
set<pair<int,int>> bridges;
vector<int> ind2com;

vector<vector<pair<int,int>>> comadjlist;
int n;
void tarjan(int node, int parent, int d, int ni){
	//cout<<node<<" "<<parent<<" "<<d<<'\n';
	depth[node]=d;
	low[node]=d;
	int lowest = n;
	bool ispar = false;
	if (ni%2==0){
		ni++;
	} else {
		ni--;
	}
	for (auto p : adjlist[node]){
		int newnode = p.first;
		int newind = p.second;
		if (ni==newind){continue;}
		if (low[newnode]==n){
			//not visited before
			tarjan(newnode,node,d+1,newind);
			if (low[newnode]>d){
				//cout<<"bridge "<<node<<" "<<newnode<<'\n';
				//is bridge
				//cout<<"erase"<<'\n'; 
				if (newind%2==0){
					bridgeedges.push_back({newind,{node,newnode}});
					bridgeedges.push_back({newind+1,{newnode,node}});
				} else {
					bridgeedges.push_back({newind,{node,newnode}});
					bridgeedges.push_back({newind-1,{newnode,node}});
				}
				//cout<<"done"<<'\n';
				bridges.insert({min(newnode,node),max(newnode,node)});
			}
		}
		low[node]=min(low[node],low[newnode]);
	}
}

void dfs(int ind, int numcom){
	ind2com[ind]=numcom;
	for (auto p : adjlist[ind]){
		//if (p.second<0){continue;}
		if (bridges.count({min(ind,p.first),max(ind,p.first)})){continue;}
		if (ind2com[p.first]==-1){dfs(p.first,numcom);}
	}
}

int kthparent[100000][20];

vector<int> upcnt;
vector<int> downcnt;
vector<char> ans;
vector<bool> visited;
int nc;
void treedfs(int node, int parent){
	visited[node]=true;
	//cout<<node<<" "<<parent<<'\n';
	for (auto p : comadjlist[node]){
		if (p.first==parent){continue;}
		depth[p.first]=depth[node]+1;
		kthparent[p.first][0]=node;
		treedfs(p.first,node);
	}
}

void decom2k(){
	for (int i = 1; i<20; i++){
		for (int x = 0; x<nc; x++){
			if (kthparent[x][i-1]==-1){
				kthparent[x][i]=-1;
			} else {
				kthparent[x][i]=kthparent[kthparent[x][i-1]][i-1];
			}
		}
	}
}

int lca(int a, int b){
	if (depth[a]<depth[b]){
		swap(a,b);
	}
	for (int i = 19; i>=0; i--){
		if (kthparent[a][i]==-1){continue;}
		if (depth[kthparent[a][i]]>=depth[b]){
			a=kthparent[a][i];
		}
	}
	//cout<<a<<" "<<b<<'\n';
	if (a==b){return a;}
	for (int i = 19; i>=0; i--){
		if (kthparent[a][i]==-1){continue;}
		if (kthparent[a][i]!=kthparent[b][i]){
			a=kthparent[a][i];
			b=kthparent[b][i];
		}
	}
	return kthparent[a][0];
}

void ansdfs(int node, int parent){
	int totup = 0;
	int totdown = 0;
	for (auto p : comadjlist[node]){
		int ind = p.first;
		if (ind==parent){continue;}
		ansdfs(ind,node);
		if (upcnt[ind]>0){
			//p.second even if node->p.first is R
			//otherwise L
			//flip val
			ans[p.second/2]=((p.second%2==0)?'L':'R');
		} else if (downcnt[ind]>0){
			//don't flip val
			ans[p.second/2]=((p.second%2==0)?'R':'L');
		}
		totup+=upcnt[ind];
		totdown+=downcnt[ind];
	}
	upcnt[node]+=totup;
	downcnt[node]+=totdown;
	//cout<<node<<" "<<upcnt[node]<<" "<<downcnt[node]<<'\n';
	assert(!(upcnt[node]>0&&downcnt[node]>0));
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int m;
	cin>>n>>m;
	adjlist.resize(n);
	depth.resize(n,0);
	low.resize(n,n);
	for (int i = 0; i<m; i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		if (a==b){continue;}
		adjlist[a].insert({b,i*2});
		adjlist[b].insert({a,i*2+1});
	}
	ans.resize(m,'B');
	for (int i = 0; i<n; i++){
		if (low[i]==n){
			tarjan(i,-1,0,-1);
		}
	}
	ind2com.resize(n,-1);
	int numcom = 0;
	for (int i = 0; i<n; i++){
		if (ind2com[i]!=-1){continue;}
		dfs(i,numcom);
		numcom++;
	}
	//cout<<numcom<<" "<<bridgeedges.size()<<'\n';
	comadjlist.resize(numcom);
	for (auto p : bridgeedges){
		comadjlist[ind2com[p.second.first]].push_back({ind2com[p.second.second],p.first});
	}
	/*for (int i = 0; i<numcom; i++){
		cout<<i<<": ";
		for (auto j : comadjlist[i]){
			cout<<j.first<<", ";
		}cout<<'\n';
	}*/
	//assert(numcom==bridgeedges.size()/2+1);
	vector<int> roots;
	nc=numcom;
	visited.resize(nc,false);
	depth.resize(nc,0);
	for (int i = 0; i<nc; i++){
		if (visited[i]){continue;}
		treedfs(i,-1);
		roots.push_back(i);
		kthparent[i][0]=-1;
	}
	decom2k();

	int p;
	cin>>p;
	upcnt.resize(nc);
	downcnt.resize(nc);
	for (int i = 0; i<p; i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		a=ind2com[a];
		b=ind2com[b];
		if (a==b){continue;}
		int l = lca(a,b);
		//cout<<a<<" "<<b<<" "<<l<<'\n';
		upcnt[a]++;
		upcnt[l]--;
		downcnt[l]--;
		downcnt[b]++;
	}
	for (int r : roots){
		ansdfs(r,-1);
	}
	for (char c : ans){
		cout<<c;
	}cout<<'\n';
}

Compilation message (stderr)

oneway.cpp: In function 'void tarjan(int, int, int, int)':
oneway.cpp:18:6: warning: unused variable 'lowest' [-Wunused-variable]
  int lowest = n;
      ^~~~~~
oneway.cpp:19:7: warning: unused variable 'ispar' [-Wunused-variable]
  bool ispar = false;
       ^~~~~

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