제출 #98547

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

oneway

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int n, m;

pair<pair<int, int>, char> edgeList[100000];

vector<pair<pair<int, int>, int> > adjList[100001];
int visOrd[100001];
int visLow[100001];
int parent[100001];
int counter;

void dfs(int node){
    visOrd[node]=visLow[node]=counter;
    counter++;
    bool countParent=false;
    for(int i=0;i<adjList[node].size();i++){
        if(visOrd[adjList[node][i].first.first]==-1){
            parent[adjList[node][i].first.first]=node;
            dfs(adjList[node][i].first.first);
        }
        if(adjList[node][i].first.first!=parent[node]||countParent){
            visLow[node]=min(visLow[node], visLow[adjList[node][i].first.first]);
            adjList[node][i].first.second=visLow[adjList[node][i].first.first]>visOrd[node]?1:0;
        }
        if(adjList[node][i].first.first==parent[node]){
            countParent=true;
        }
    }
}

int parent2[100001], depth[100001];

int root(int a){
    int b=a;
    while(b!=parent2[b]){
        b=parent2[b];
    }
    return parent2[a]=b;
}

bool isCon(int a, int b){
    return root(a)==root(b);
}

void join(int a, int b){
    if(depth[root(a)]<root(b)){
        parent2[root(a)]=root(b);
    }
    else if(depth[root(b)]<root(a)){
        parent2[root(b)]=root(a);
    }
    else{
        parent2[root(b)]=root(a);
        depth[root(a)]++;
    }
}

vector<pair<int, int> > adjList2[100001];
int firstVis2[100001];
int visOrd2[199999];
int depth2[100001];
int LCATable[18][199999];
int counter2;

void dfs2(int node){
    firstVis2[node]=counter2;
    visOrd2[counter2]=node;
    counter2++;
    for(int i=0;i<adjList2[node].size();i++){
        if(firstVis2[adjList2[node][i].first]==-1){
            depth2[adjList2[node][i].first]=depth2[node]+1;
            dfs2(adjList2[node][i].first);
            visOrd2[counter2]=node;
            counter2++;
        }
    }
}

void initLCA(){
    for(int i=0;i<2*n-1;i++){
        LCATable[0][i]=i;
    }
    for(int i=1;(1<<i)<=2*n-1;i++){
        for(int j=0;j+(1<<i)<=2*n-1;j++){
            if(depth2[visOrd2[LCATable[i-1][j]]]>depth2[visOrd2[LCATable[i-1][j+(1<<(i-1))]]]){
                LCATable[i][j]=LCATable[i-1][j+(1<<(i-1))];
            }
            else{
                LCATable[i][j]=LCATable[i-1][j];
            }
        }
    }
}

int LCA(int a, int b){
    int l=min(firstVis2[a], firstVis2[b]), r=max(firstVis2[a], firstVis2[b]);
    int mini=r, diff=r-l;
    for(int i=0;i<18;i++){
        if(diff&(1<<i)){
            if(depth2[visOrd2[LCATable[i][l]]]<depth2[visOrd2[mini]]){
                mini=LCATable[i][l];
            }
            l+=(1<<i);
        }
    }
    return visOrd2[mini];
}

bool vis3[100001];
pair<int, int> dir[100001];

void dfs3(int node){
    vis3[node]=true;
    for(int i=0;i<adjList2[node].size();i++){
        if(!vis3[adjList2[node][i].first]){
            dfs3(adjList2[node][i].first);
            if(depth2[dir[adjList2[node][i].first].first]<depth2[dir[node].first]){
                dir[node]=dir[adjList2[node][i].first];
            }
            if(depth2[dir[adjList2[node][i].first].first]<depth2[adjList2[node][i].first]){
                if((depth2[root(edgeList[adjList2[node][i].second].first.first)]<depth2[root(edgeList[adjList2[node][i].second].first.second)])==(dir[adjList2[node][i].first].second==-1)){
                    edgeList[adjList2[node][i].second].second='L';
                }
                else{
                    edgeList[adjList2[node][i].second].second='R';
                }
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;i++){
        scanf("%d%d", &edgeList[i].first.first, &edgeList[i].first.second);
        edgeList[i].second='B';
        adjList[edgeList[i].first.first].push_back(make_pair(make_pair(edgeList[i].first.second, -1), i));
        adjList[edgeList[i].first.second].push_back(make_pair(make_pair(edgeList[i].first.first, -1), i));
    }
    for(int i=1;i<n+1;i++){
        visOrd[i]=-1;
    }
    counter=0;
    parent[1]=0;
    dfs(1);
    for(int i=1;i<n+1;i++){
        parent2[i]=i;
        depth[i]=1;
    }
    for(int i=1;i<n+1;i++){
        for(int j=0;j<adjList[i].size();j++){
            if(adjList[i][j].first.second==0){
                if(!isCon(i, adjList[i][j].first.first)){
                    join(i, adjList[i][j].first.first);
                }
            }
        }
    }
    for(int i=1;i<n+1;i++){
        for(int j=0;j<adjList[i].size();j++){
            if(adjList[i][j].first.second==1){
                adjList2[root(i)].push_back(make_pair(root(adjList[i][j].first.first), adjList[i][j].second));
                adjList2[root(adjList[i][j].first.first)].push_back(make_pair(root(i), adjList[i][j].second));
            }
        }
    }
    for(int i=1;i<n+1;i++){
        firstVis2[i]=-1;
    }
    counter2=0;
    depth2[root(1)]=1;
    dfs2(root(1));
    initLCA();
    int p;
    scanf("%d", &p);
    for(int i=1;i<n+1;i++){
        dir[i]=make_pair(i, 0);
    }
    while(p--){
        int x, y;
        scanf("%d%d", &x, &y);
        int temp=LCA(root(x), root(y));
        if(depth2[temp]<depth2[dir[root(x)].first]){
            dir[root(x)]=make_pair(temp, -1);
        }
        if(depth2[temp]<depth2[dir[root(y)].first]){
            dir[root(y)]=make_pair(temp, 1);
        }
    }
    for(int i=1;i<n+1;i++){
        vis3[i]=false;
    }
    dfs3(root(1));
    for(int i=0;i<m;i++){
        printf("%c", edgeList[i].second);
    }
    return 0;
}

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

oneway.cpp: In function 'void dfs(int)':
oneway.cpp:21:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adjList[node].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int)':
oneway.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adjList2[node].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs3(int)':
oneway.cpp:119:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adjList2[node].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:156:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<adjList[i].size();j++){
                     ~^~~~~~~~~~~~~~~~~~
oneway.cpp:165:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<adjList[i].size();j++){
                     ~^~~~~~~~~~~~~~~~~~
oneway.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &edgeList[i].first.first, &edgeList[i].first.second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p);
     ~~~~~^~~~~~~~~~
oneway.cpp:186:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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