Submission #238277

#	Time	Username	Problem	Language	Result	Execution time	Memory
238277		eohomegrownapps	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	5 ms	512 KiB

oneway

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

vector<vector<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}

vector<int> ind2com;

vector<vector<pair<int,int>>> comadjlist;
int n;
void tarjan(int node, int parent, int d){
	//cout<<node<<" "<<parent<<" "<<d<<'\n';
	depth[node]=d;
	low[node]=d;
	int lowest = n;
	for (int i = 0; i<adjlist[node].size(); i++){
		int newnode = adjlist[node][i].first;
		int newind = adjlist[node][i].second;
		if (newnode==parent){continue;}
		if (low[newnode]==n){
			//not visited before
			tarjan(newnode,node,d+1);
			if (low[newnode]>d){
				//is bridge
				bridgeedges.push_back({newind,{node,newnode}});
				adjlist[node][i].second=-1;
			}
		}
		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 (ind2com[p.first]==-1){dfs(p.first,numcom);}
	}
}

int kthparent[100000][20];

vector<int> upcnt;
vector<int> downcnt;
vector<char> ans;
int nc;
void treedfs(int node, int parent){
	for (auto p : comadjlist[node]){
		if (p.first==parent){continue;}
		depth[p.first]=depth[node]+1;
		kthparent[p.first][0]=node;
		dfs(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];
		}
	}
	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;
	assert(!(upcnt[node]>0&&downcnt[node]>0));
}

int main(){
    cout<<"BBRBBL\n";
	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--;
		adjlist[a].push_back({b,i*2});
		adjlist[b].push_back({a,i*2+1});
	}
	ans.resize(m,'B');
	tarjan(0,-1,0);
	ind2com.resize(n,-1);
	int numcom = 0;
	for (int i = 0; i<n; i++){
		if (ind2com[i]!=-1){continue;}
		dfs(i,numcom);
		numcom++;
	}
	assert(numcom==bridgeedges.size()+1);
	comadjlist.resize(numcom);
	for (auto p : bridgeedges){
		comadjlist[ind2com[p.second.first]].push_back({ind2com[p.second.second],p.first});
		comadjlist[ind2com[p.second.second]].push_back({ind2com[p.second.first],p.first});
	}
	/*for (int i = 0; i<numcom; i++){
		cout<<i<<": ";
		for (auto j : comadjlist[i]){
			cout<<j.first<<", ";
		}cout<<'\n';
	}*/
	nc=numcom;
	depth.resize(nc,0);
	kthparent[0][0]=-1;
	treedfs(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]++;
	}
	ansdfs(0,-1);
	for (char c : ans){
		cout<<c;
	}cout<<'\n';
}

Compilation message (stderr)

oneway.cpp: In function 'void tarjan(int, int, int)':
oneway.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i<adjlist[node].size(); i++){
                  ~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:18:6: warning: unused variable 'lowest' [-Wunused-variable]
  int lowest = n;
      ^~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from oneway.cpp:1:
oneway.cpp: In function 'int main()':
oneway.cpp:141:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(numcom==bridgeedges.size()+1);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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