# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
419006 | RambaXGorilla | One-Way Streets (CEOI17_oneway) | C++17 | 7 ms | 9268 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<utility>
using namespace std;
int N, M, P;
pair <int,int> roads[100010];
pair <int,int> save[100010];
int imps[100010][3];
int dfsCnt = 0;
bool vis[100010];
int pows[20];
int dfsNums[100010];
int dfsLows[100010];
int dfsPars[100010];
int cons[100010];
int treePars[100010];
int dirs[100010];
char trans[] = {'L', 'B', 'R'};
vector <int> adjGraph[100010];
vector <int> adjTree[100010];
vector <int> adjCycles[100010];
map < pair <int,int>, int> goBack;
map < pair <int,int>, bool> bridges;
void getBridges(int u){
dfsNums[u] = dfsLows[u] = dfsCnt++;
for(int i = 0;i < adjGraph[u].size();i++){
int v = adjGraph[u][i];
if(dfsNums[v] == -1){
dfsPars[v] = u;
getBridges(v);
if(dfsLows[v] > dfsNums[u]){
bridges[make_pair(min(u, v), max(u, v))] = true;
}
dfsLows[u] = min(dfsLows[u], dfsLows[v]);
}
else if(dfsPars[u] != v || goBack[make_pair(min(u, v), max(u, v))] > 1){
dfsLows[u] = min(dfsLows[u], dfsNums[v]);
}
}
}
void getCycles(int u, int r){
cons[u] = r;
for(int i = 0;i < adjCycles[u].size();i++){
int v = adjCycles[u][i];
if(cons[v] == -1){
getCycles(v, r);
}
}
}
void getTreePars(int u){
for(int i = 0;i < adjTree[u].size();i++){
int v = adjTree[u][i];
if(treePars[v] == -1){
treePars[v] = u;
getTreePars(v);
}
}
}
void addTreeDirs(int u){
vis[u] = true;
for(int i = 0;i < adjTree[u].size();i++){
int v = adjTree[u][i];
if(!vis[v]){
addTreeDirs(v);
dirs[u] += dirs[v];
}
}
}
int main(){
scanf("%d%d",&N,&M);
for(int i = 0;i < M;i++){
scanf("%d%d",&roads[i].first,&roads[i].second);
save[i] = roads[i];
if(roads[i].first > roads[i].second){
swap(roads[i].first, roads[i].second);
}
else if(roads[i].first == roads[i].second){
continue;
}
goBack[roads[i]] += 1;
if(goBack[roads[i]] == 1){
adjGraph[roads[i].first].push_back(roads[i].second);
adjGraph[roads[i].second].push_back(roads[i].first);
}
}
scanf("%d",&P);
for(int i = 0;i < P;i++){
scanf("%d%d",&imps[i][0],&imps[i][1]);
}
int length = 1;
for(int i = 0;i < 20;i++){
pows[i] = length;
length *= 2;
}
for(int i = 0;i < 100010;i++){
dfsNums[i] = -1;
cons[i] = -1;
treePars[i] = -1;
dirs[i] = 0;
vis[i] = false;
}
for(int i = 1;i < N + 1;i++){
if(dfsNums[i] == -1){
getBridges(i);
}
}
for(int i = 0;i < M;i++){
if(!bridges[roads[i]]){
adjCycles[roads[i].first].push_back(roads[i].second);
adjCycles[roads[i].second].push_back(roads[i].first);
}
}
int cnt = 0;
for(int i = 1;i < N + 1;i++){
if(cons[i] == -1){
cnt += 1;
getCycles(i, cnt);
}
}
for(int i = 0;i < M;i++){
if(bridges[roads[i]]){
adjTree[cons[roads[i].first]].push_back(cons[roads[i].second]);
adjTree[cons[roads[i].second]].push_back(cons[roads[i].first]);
}
}
for(int i = 1;i < cnt + 1;i++){
if(treePars[i] == -1){
treePars[i] = 0;
getTreePars(i);
}
}
for(int i = 0;i < P;i++){
dirs[cons[imps[i][0]]] = 1;
dirs[cons[imps[i][1]]] = -1;
}
for(int i = 1;i < cnt + 1;i++){
if(!vis[i]){
addTreeDirs(i);
}
}
for(int i = 0;i < M;i++){
int u = save[i].first;
int v = save[i].second;
int uT = cons[u];
int vT = cons[v];
if(uT == vT){
printf("B");
continue;
}
int d;
if(treePars[uT] == vT){
d = dirs[uT];
}
else{
d = dirs[vT] * -1;
}
if(d != 0){
d /= abs(d);
}
printf("%c",trans[d + 1]);
}
printf("\n");
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |