제출 #246812

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

oneway

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int p[100005], low[100005], num[100005];
int ct = 1;
int n,m,q;
vector<int> G[100005];
vector<int> _G[200005];
int col[100005];
int brid[100005];
int d[100005];
int P[100005][20];
int U[100005], V[100005];
int ans[100005];
int cct = 1;
vector<ii> hm[100005];
vector<int> ord;
map<ii, int> countedg;
void dfs(int u){
    low[u] = num[u] = ct++;
    for (auto v : G[u]){
        if (num[v] == -1){
            p[v] = u;
            dfs(v);
            if (low[v] > num[u]){
                //printf("%d %d is a bridge\n",u,v);
                brid[v] = 1;
            }
            low[u] = min(low[u],low[v]);
        }
        else if (p[u] != v){
            low[u] = min(low[u],num[v]);
        }
    }
}
void dfs2(int u){
    for (auto v : G[u]){
        if (p[v] == u){
            if (brid[v] && countedg[ii(min(u,v),max(u,v))] == 1) continue;
            col[v] = col[u];
            dfs2(v);
        }
    }
}
void dfs3(int u){
    ord.push_back(u);
    for (auto v : _G[u]){
        if (P[v][0] == -1){
            //printf("%d -> %d\n",u,v);
            P[v][0] = u;
            d[v] = d[u]+1;
            dfs3(v);
        }
    }
}
int lca(int u, int v){
    if (d[u] < d[v]) swap(u,v);
    int dif = d[u]-d[v];
    for (int i = 0; i < 20; i++){
        if (dif>>i&1){
            u = P[u][i];
        }
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; i--){
        if (P[u][i] != -1 && P[v][i] != -1 && P[u][i] != P[v][i]){
            u = P[u][i], v = P[v][i];
        }
    }
    assert(P[u][0] == P[v][0]);
    return P[u][0];
}
int main(){
    scanf("%d%d",&n,&m);
    memset(num,-1,sizeof(num));
    for (int i = 0; i < m; i++){
        scanf("%d%d",&U[i],&V[i]);
        int che = ++countedg[ii(min(U[i],V[i]),max(U[i],V[i]))];
        if (U[i] == V[i] || che > 1) continue;
        G[U[i]].push_back(V[i]);
        G[V[i]].push_back(U[i]);
    }
    dfs(1);
    for (int i = 1; i <= n; i++){
        if (col[i] == 0){
            col[i] = cct++;
            dfs2(i);
        }
    }
    //for (int i = 1; i <= n; i++){ printf("%d ",col[i]); }
    for (int u = 1; u <= n; u++){
        for (auto v : G[u]){
            if (col[v] != col[u]){
                _G[col[u]].push_back(col[v]);
            }
        }
    }
    memset(P,-1,sizeof(P));
    for (int i = 1; i < cct; i++){
        if (P[i][0] == -1){
            P[i][0] = i;
            dfs3(i);
        }
    }
    for (int k = 1; k < 20; k++){
        for (int i = 1; i < cct; i++){
            if (P[i][k-1] == -1) break;
            P[i][k] = P[P[i][k-1]][k-1];
        }
    }
    scanf("%d",&q);
    for (int i = 0; i < q; i++){
        int a, b;
        scanf("%d%d",&a,&b);
        if (col[a] == col[b]) continue;
        else{
            a = col[a];
            b = col[b];
            int c = lca(a,b);
            //printf("%d %d %d\n",a,c,b);
            if (c != a) hm[c].push_back({a,1});
            if (c != b) hm[c].push_back({b,-1});
        }
    }
    for (auto x:  ord){
        for (auto cur : hm[x]){
            int u = cur.first, dir = cur.second;
            while (ans[u] == 0 && u != x){
                //printf("%d -> %d with %d\n",u,P[u][0],dir);
                ans[u] = dir;
                u = P[u][0];
            }
        }
    }
    for (int i = 0; i < m; i++){
        int u = U[i], v = V[i];
        if (col[u] == col[v]){
            printf("B");
        }
        else{
            u = col[u], v = col[v];
            if (d[v] > d[u]){
                if (ans[v] == 1) printf("L");
                else if (ans[v] == -1) printf("R");
                else printf("B");
            }
            else{
                if (ans[u] == 1) printf("R");
                else if (ans[u] == -1) printf("L");
                else printf("B");
            }
        }
    }

}

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

oneway.cpp: In function 'int main()':
oneway.cpp:74: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:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&U[i],&V[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
oneway.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

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