oj.uz

답안 #397055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397055 2021-05-01T08:58:13 Z Nicholas_Patrick One-Way Streets (CEOI17_oneway) C++17
0 / 100
 2 ms 332 KB 
#include <cstdio>
#include <queue>
#include <string>
using namespace std;

struct edge{
	int f, t, i;
};
string ans;
//graph 1
vector<vector<edge>> adjLis1;
vector<int> dt, low;
int t;
vector<int> p;
int par(int x){
	if(p[x]==x)
		return x;
	return p[x]=par(p[x]);
}
vector<int> pp;
int ppar(int x){
	if(pp[x]==x)
		return x;
	return pp[x]=ppar(pp[x]);
}
//graph 2
vector<edge> edgeLis;
vector<vector<edge>> adjLis2;
//graph 1: graph 2
void dfs1(int x, int pi=-1){
	dt[x]=low[x]=t++;
	for(auto i: adjLis1[x]){
		int y=i.f+i.t-x;
		if(dt[y]==0){
			dfs1(y, i.i);
			low[x]=min(low[x], low[y]);
			if(dt[x]<low[y]){
				//bridge
				edgeLis.push_back(i);
			}else{
				//not bridge
				p[par(x)]=par(y);
				// printf("merge %d %d\n", x, y);
			}
		}else if(i.i!=pi){
			low[x]=min(low[x], dt[y]);
		}
	}
}
//graph 1
void dfs2(int x){
	dt[x]=1;
	for(auto i: adjLis1[x]){
		int y=i.f+i.t-x;
		if(p[x]==p[y])
			ans[i.i]='B';
		if(dt[y]==0)
			dfs2(y);
	}
}
//graph 2
vector<int> parent, depth, jump;
vector<int> direction;//012 + 048 --> parent/jump nothing, up, down
//yes, I know, p, par, pi, and parent all mean parent
void dfs3(int x){
	for(auto& i: adjLis2[x]){
		int y=i.f+i.t-x;
		if(y==parent[x])
			continue;
		parent[y]=x;
		depth[y]=depth[x]+1;
		int j=jump[x];
		jump[y]=depth[jump[j]]+depth[x]==depth[j]<<1?jump[j]:x;
		dfs3(y);
	}
}
void direct(int x, int y){
	if(depth[x]<depth[y]){
		while(depth[x]<depth[y]){
			if(depth[x]<=depth[jump[y]]){
				direction[y]|=8;
				y=jump[y];
			}else{
				direction[y]|=2;
				y=parent[y];
			}
		}
	}else{
		while(depth[x]>depth[y]){
			if(depth[x]>=depth[jump[y]]){
				direction[x]|=4;
				x=jump[x];
			}else{
				direction[x]|=1;
				x=parent[x];
			}
		}
	}
	if(x==y){
		// printf("LCA a: %d\n", x);
		return;
	}
	while(parent[x]!=parent[y]){
		if(jump[x]!=jump[y]){
			direction[x]|=4;
			x=jump[x];
			direction[y]|=8;
			y=jump[y];
		}else{
			direction[x]|=1;
			x=parent[x];
			direction[y]|=2;
			y=parent[y];
		}
	}
	direction[x]|=1;
	direction[y]|=2;
	// printf("LCA b: %d\n", parent[x]);
}
void dfs4(int x){
	for(auto& i: adjLis2[x]){
		int y=i.f+i.t-x;
		if(y==parent[x])
			continue;
		dfs4(y);
		if(jump[y]!=x){
			direction[x]|=direction[y]&12;
			direction[jump[x]]|=direction[y]&12;
		}
		if(direction[y]&5){
			if(i.f==y){
				ans[i.i]='R';
			}else{
				ans[i.i]='L';
			}
		}
		if(direction[y]&10){
			if(i.f==y){
				ans[i.i]='L';
			}else{
				ans[i.i]='R';
			}
		}
	}
}
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	ans=string(m, 'B');
	adjLis1.resize(n);
	pp.resize(n);
	for(int i=n; i--;)pp[i]=i;
	for(int i=0; i<m; i++){
		edge inp;
		scanf("%d%d", &inp.f, &inp.t), inp.f--, inp.t--;
		pp[ppar(inp.f)]=ppar(inp.t);
		inp.i=i;
		adjLis1[inp.f].push_back(inp);
		adjLis1[inp.t].push_back(inp);
	}
	dt.assign(n, 0);
	low.resize(n);
	t=1;
	p.resize(n);
	for(int i=n; i--;)p[i]=i;
	for(int i=n; i--;){
		if(ppar(i)==i)
			dfs1(i);
	}
	for(int& i: p)
		i=par(i);
	dt.assign(n, 0);
	for(int i=n; i--;){
		if(pp[i]==i)
			dfs2(i);
	}
	adjLis2.resize(n);
	for(auto i: edgeLis){
		i.f=p[i.f], i.t=p[i.t];
		// printf("edge %d-%d\n", i.f, i.t);
		adjLis2[i.f].push_back(i);
		adjLis2[i.t].push_back(i);
	}
	parent.resize(n);
	jump.resize(n);
	depth.resize(n);
	for(int i=n; i--;){
		if(pp[i]==i){
			int root=p[i];
			parent[root]=jump[root]=root;
			depth[root]=0;
			dfs3(root);
		}
	}
	direction.assign(n, 0);
	int q;
	scanf("%d", &q);
	while(q--){
		int x, y;
		scanf("%d%d", &x, &y), x--, y--;
		x=p[x], y=p[y];
		direct(x, y);
	}
	for(int i=n; i--;){
		if(pp[i]==i){
			int root=p[i];
			dfs4(root);
		}
	}
	printf("%s\n", ans.c_str());
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  148 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  155 |   scanf("%d%d", &inp.f, &inp.t), inp.f--, inp.t--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:197:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  197 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:200:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  200 |   scanf("%d%d", &x, &y), x--, y--;
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -