제출 #137069

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

oneway

#include <bits/stdc++.h>
using namespace std;

const int MN = 1e5+5, LG = 19;
int N, M, Q, S, i, x, y, vis[MN][2], sp[MN][LG], cmp[MN], st[MN], nxt, ans[MN], u[MN], d[MN], dep[MN];
vector<pair<int,int>> adj[MN], cadj[MN];
stack<int> s;
pair<int,int> ree[MN];
string ans2;

void dfs(int n,int id){
    vis[n][0]=vis[n][1]=++nxt;
    st[n]=1; s.push(n);
    for(auto v : adj[n]){
        if(v.second==id) continue;
        if(!vis[v.first][0]){
            dfs(v.first, v.second);
            vis[n][1]=min(vis[n][1],vis[v.first][1]);
        }
        else if(st[v.first]){
            vis[n][1]=min(vis[n][1],vis[v.first][0]);
        }
    }
    if(vis[n][0]==vis[n][1]){
        S++;
        while(s.size()&&s.top()!=n){
            int x = s.top(); s.pop();
            cmp[x] = S;
        }
        int x = s.top(); s.pop();
        cmp[x] = S;
    }
}

void ddfs(int n,int p,int d){
    sp[n][0] = p; dep[n] = d;
    for(auto v : cadj[n]){
        if(v.first==p) continue;
        ddfs(v.first, n, d+1);
    }
}

int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LG-1;i>=0;i--){
        if((1<<i)<=dep[x]-dep[y])
            x = sp[x][i];
    }
    if(x==y) return x;
    for(int i=LG-1;i>=0;i--){
        if(sp[x][i]!=sp[y][i]){
            x = sp[x][i];
            y = sp[y][i];
        }
    }
    return sp[x][0];
}

pair<int,int> solve(int n,int p){
    int a=u[n], b=d[n];
    for(auto v : cadj[n]){
        if(v.first==p) continue;
        auto t = solve(v.first, n);
        a += t.first, b += t.second;
    }
    if(a>0){
        for(int i=0;i<cadj[n].size();i++){
            if(cadj[n][i].first==p){
                ans[cadj[n][i].second]=1;
                break;
            }
        }
    }
    else if(b>0){
        for(int i=0;i<cadj[n].size();i++){
            if(cadj[n][i].first==p){
                ans[cadj[n][i].second]=2;
                break;
            }
        }
    }
    return make_pair(a,b);
}

int main(){
    for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
        scanf("%d%d",&x,&y);
        adj[x].push_back({y,i});
        adj[y].push_back({x,i});
        ree[i]={x,y};
    }
    for(i=1;i<=N;i++){
        if(!vis[i][0]) dfs(i,0);
    }
    for(i=1;i<=N;i++){
        for(auto v : adj[i]){
            if(cmp[v.first]!=cmp[i])
                cadj[cmp[i]].push_back({cmp[v.first],v.second});
        }
    }
    ddfs(1,0,1);
    for(int j=1;j<LG;j++){
        for(i=1;i<=S;i++)
            sp[i][j]=sp[sp[i][j-1]][j-1];
    }
    for(scanf("%d",&Q),i=1;i<=Q;i++){
        scanf("%d%d",&x,&y);
        if(cmp[x]==cmp[y]) continue;
        x = cmp[x], y = cmp[y];
        int a = lca(x,y);
        u[x]++; u[a]--;
        d[y]++; d[a]--;
    }
    solve(1, 0);
    for(i=1;i<=M;i++){
        if(ans[i]){
            tie(x,y)=ree[i];
            if(dep[cmp[x]]<dep[cmp[y]]){
                if(ans[i]==2) ans2.push_back('R');
                else ans2.push_back('L');
            }
            else{
                if(ans[i]==2) ans2.push_back('L');
                else ans2.push_back('R');
            }
        }
        else ans2.push_back('B');
    }
    printf("%s\n",ans2.c_str());
    return 0;
}

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

oneway.cpp: In function 'std::pair<int, int> solve(int, int)':
oneway.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<cadj[n].size();i++){
                     ~^~~~~~~~~~~~~~~
oneway.cpp:75:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<cadj[n].size();i++){
                     ~^~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:86:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
         ~~~~~~~~~~~~~~~~~~~^~~~
oneway.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~
oneway.cpp:106:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d",&Q),i=1;i<=Q;i++){
         ~~~~~~~~~~~~~~^~~~
oneway.cpp:107: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