| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 397034 | 2021-05-01T08:05:37 Z | Nicholas_Patrick | One-Way Streets (CEOI17_oneway) | C++17 | 1 ms | 204 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=0, int pi=-1){
dt[x]=low[x]=t;t+=2;
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]-1);
}
}
}
//graph 1
void dfs2(int x=0){
dt[x]++;
for(auto i: adjLis1[x]){
int y=i.f+i.t-x;
if(par(x)==par(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]<=jump[depth[y]]){
direction[y]|=8;
y=jump[y];
}else{
direction[y]|=2;
y=parent[y];
}
}
}else{
while(depth[x]>depth[y]){
if(depth[x]>=jump[depth[y]]){
direction[x]|=4;
x=jump[x];
}else{
direction[x]|=1;
x=parent[x];
}
}
}
if(x==y){
// printf("LCA: %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: %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();
}
dt.assign(n, 0);
for(int i=n; i--;){
if(pp[i]==i)
dfs2();
}
for(int& i: p)
i=par(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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 204 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 204 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 204 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |