제출 #199517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199517		algorithm16	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	7 ms	3580 KiB

oneway

#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,p,bio[100005],d[100005],t=1,lo[100005],parent[100005],depth[100005],par2[25][100005],arr[100005],ind[100005];
vector <int> v[100005];
vector <pair<int,int> > v2;
vector <pair<int,int> > v3;
vector <pair<int,int> > p1;
map <pair<int,int>,int> m1;
string sol;
int find_par(int x) {
	if(x==parent[x]) return x;
	int par=find_par(parent[x]);
	parent[x]=par;
	return par;
}
void spoji(int x,int y) {
	if(x>y) swap(x,y);
	//cout << x << " " << y << "\n";
	x=find_par(x);
	y=find_par(y);
	//cout << x << " " << y << "\n";
	if(x==y) return;
	if(depth[x]==depth[y]) depth[x]+=1;
	if(depth[x]>depth[y]) parent[y]=x;
	else parent[x]=y;
}
int dfs(int x,int par) {
	bio[x]=1;
	d[x]=t;
	t+=1;
	int ret=1e9;
	for(int i=0;i<v[x].size();i++) {
		if(v[x][i]==par) continue;
		if(bio[v[x][i]]) {
			//sol[abs(m1[make_pair(x,v[x][i])])-1]='B';
			ret=min(ret,d[v[x][i]]);
			spoji(x,v[x][i]);
		}
		else {
			ret=min(ret,dfs(v[x][i],x));
			if(d[x]<lo[v[x][i]]) {
				v3.push_back(make_pair(min(x,v[x][i]),max(x,v[x][i])));
				sol[abs(m1[make_pair(x,v[x][i])])-1]=' ';
			}
			else {
				//cout << "abc " << x << " " << v[x][i] << "\n";
				spoji(x,v[x][i]);
				//sol[abs(m1[make_pair(x,v[x][i])])-1]='B';
			}
		}
	}
	lo[x]=ret;
	return ret;
}
void dfs2(int x,int par,int d1) {
	par2[0][x]=par;
	depth[x]=d1;
	for(int i=0;i<v[x].size();i++) {
		if(v[x][i]==par) continue;
		dfs2(v[x][i],x,d1+1);
	}
}
int lca(int a,int b) {
	if(depth[a]<depth[b]) swap(a,b);
	for(int i=20;i>=0;i--) {
		if((depth[a]-depth[b]) & (1 << i)) a=par2[i][a];
	}
	if(a==b) return a;
	for(int i=20;i>=0;i--) {
		if(par2[i][a]==par2[i][b]) continue;
		a=par2[i][a];
		b=par2[i][b];
	}
	return par2[0][a];
}
int dfs3(int x,int par) {
	int ret=arr[x];
	for(int i=0;i<v[x].size();i++) {
		if(v[x][i]==par) continue;
		ret+=dfs3(v[x][i],x);
	}
	//cout << x << " " << ret << " " << m1[make_pair(x,par)] << "\n";
	if(x) {
		if(ret==0 && sol[abs(m1[make_pair(x,par)])-1]!='L' && sol[abs(m1[make_pair(x,par)])-1]!='R') sol[abs(m1[make_pair(x,par)])-1]='B';
		else if(ret==0) return ret;
		else if(ret<0) {
			if(m1[make_pair(x,par)]>0) sol[m1[make_pair(x,par)]-1]='R';
			else sol[-m1[make_pair(x,par)]-1]='L';
		}
		else {
			//cout << x << " " << par << " " << ret << " " << m1[make_pair(x,par)] << "\n";
			if(m1[make_pair(x,par)]<0) sol[-m1[make_pair(x,par)]-1]='R';
			else sol[m1[make_pair(x,par)]-1]='L';
		}
	}
	return ret;
}
int main()
{
	cin >> n >> m;
	v2.clear();
	v3.clear();
	for(int i=0;i<n;i++) {
		depth[i]=1;
		parent[i]=i;
	}
	for(int j=0;j<m;j++) {
		sol+='B';
		int a,b;
		cin >> a >> b;
		m1[make_pair(a-1,b-1)]=j+1;
		m1[make_pair(b-1,a-1)]=-j-1;
		v2.push_back(make_pair(a-1,b-1));
		v[a-1].push_back(b-1);
		v[b-1].push_back(a-1);
	}
	cin >> p;
	for(int i=0;i<p;i++) {
		int a,b;
		cin >> a >> b;
		p1.push_back(make_pair(a-1,b-1));
	}
	dfs(0,-1);
	/*for(int i=0;i<v3.size();i++) {
		cout << v3[i].first << " " << v3[i].second << "\n";
	}*/
	for(int i=0;i<n;i++) {
		v[i].clear();
	}
	for(int i=0;i<m;i++) {
		if(find_par(v2[i].first)==find_par(v2[i].second)) continue;
		v[find_par(v2[i].first)].push_back(find_par(v2[i].second));
		v[find_par(v2[i].second)].push_back(find_par(v2[i].first));
		m1[make_pair(find_par(v2[i].first),find_par(v2[i].second))]=i+1;
		m1[make_pair(find_par(v2[i].second),find_par(v2[i].first))]=-i-1;
		ind[v2[i].first]=find_par(v2[i].first);
		ind[v2[i].second]=find_par(v2[i].second);
	}
	/*for(int i=0;i<n;i++) {
		cout << ind[i] << " ";
	}
	cout << "\n";*/
	memset(depth,0,sizeof(depth));
	dfs2(0,-1,0);
	for(int i=1;i<20;i++) {
		for(int j=0;j<n;j++) {
			par2[i][j]=par2[i-1][par2[i-1][j]];
		}
	}
	for(int i=0;i<p;i++) {
		arr[ind[p1[i].first]]-=1;
		arr[lca(ind[p1[i].first],ind[p1[i].second])]+=1;
		//cout << ind[p1[i].first] << " " << ind[p1[i].second] << " " << lca(ind[p1[i].first],ind[p1[i].second]) << "\n";
	}
	dfs3(0,-1);
	//cout << sol << "\n";
	memset(arr,0,sizeof(arr));
	for(int i=0;i<p;i++) {
		arr[ind[p1[i].second]]+=1;
		arr[lca(ind[p1[i].first],ind[p1[i].second])]-=1;
		//cout << p1[i].first << " " << p1[i].second << " " << lca(p1[i].first,p1[i].second) << "\n";
	}
	dfs3(0,-1);
	cout << sol;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'int dfs(int, int)':
oneway.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int, int)':
oneway.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp: In function 'int dfs3(int, int)':
oneway.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~

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