Submission #238353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238353	2020-06-10T20:38:21 Z	eohomegrownapps	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	449 ms	47268 KB

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

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.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	6 ms	768 KB	Output is correct
5	Correct	6 ms	768 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	6 ms	768 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	6 ms	512 KB	Output is correct
10	Correct	5 ms	512 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	6 ms	768 KB	Output is correct
5	Correct	6 ms	768 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	6 ms	768 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	6 ms	512 KB	Output is correct
10	Correct	5 ms	512 KB	Output is correct
11	Correct	138 ms	13944 KB	Output is correct
12	Correct	145 ms	15840 KB	Output is correct
13	Correct	234 ms	18680 KB	Output is correct
14	Correct	240 ms	25136 KB	Output is correct
15	Correct	270 ms	27440 KB	Output is correct
16	Correct	263 ms	38696 KB	Output is correct
17	Correct	237 ms	41324 KB	Output is correct
18	Correct	254 ms	38692 KB	Output is correct
19	Correct	274 ms	43044 KB	Output is correct
20	Correct	108 ms	17400 KB	Output is correct
21	Correct	101 ms	15992 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	6 ms	768 KB	Output is correct
5	Correct	6 ms	768 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	6 ms	768 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	6 ms	512 KB	Output is correct
10	Correct	5 ms	512 KB	Output is correct
11	Correct	138 ms	13944 KB	Output is correct
12	Correct	145 ms	15840 KB	Output is correct
13	Correct	234 ms	18680 KB	Output is correct
14	Correct	240 ms	25136 KB	Output is correct
15	Correct	270 ms	27440 KB	Output is correct
16	Correct	263 ms	38696 KB	Output is correct
17	Correct	237 ms	41324 KB	Output is correct
18	Correct	254 ms	38692 KB	Output is correct
19	Correct	274 ms	43044 KB	Output is correct
20	Correct	108 ms	17400 KB	Output is correct
21	Correct	101 ms	15992 KB	Output is correct
22	Correct	449 ms	42364 KB	Output is correct
23	Correct	434 ms	39844 KB	Output is correct
24	Correct	318 ms	39848 KB	Output is correct
25	Correct	338 ms	47268 KB	Output is correct
26	Correct	324 ms	41768 KB	Output is correct
27	Correct	309 ms	39972 KB	Output is correct
28	Correct	152 ms	11128 KB	Output is correct
29	Correct	154 ms	17404 KB	Output is correct
30	Correct	151 ms	17272 KB	Output is correct
31	Correct	134 ms	17912 KB	Output is correct
32	Correct	183 ms	26928 KB	Output is correct