제출 #148090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148090		WhipppedCream	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	254 ms	30668 KiB

oneway

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 1e5+5;
vii adj[maxn];
vii tree[maxn];
ii e[maxn];
bool isB[maxn];
int num[maxn];
int low[maxn];
int bcc[maxn];
int dp[22][maxn];
int ans[maxn];
int link[maxn];
int sw[maxn];
int dep[maxn];
int chil[maxn];
int cnt;
queue<int> Q;
void dfs(int u, int id)
{
    num[u] = low[u] = ++cnt;
    for(auto edge : adj[u])
    {
        int v = edge.X, f = edge.Y;
        if(!num[v])
        {
            dfs(v, f);
            low[u] = min(low[u], low[v]);
            if(low[v]> num[u])
            {
                isB[f] = true;
            }
        }
        else if(f != id) low[u] = min(low[u], num[v]);
    }
}
void play(int u)
{
    bcc[u] = cnt;
    for(auto edge : adj[u])
    {
        int v = edge.X, id = edge.Y;
        if(!isB[id] && !bcc[v]) play(v);
    }
}
void dfsT(int u, int p)
{
    int has = 0;
    for(auto edge : tree[u])
    {
        int v = edge.X, id = edge.Y;
        if(v == p) continue;
        dp[0][v] = u;
        dep[v] = 1+dep[u];
        link[v] = id;
        has = 1;
        dfsT(v, u);
        chil[u]++;
    }
    if(!has) Q.push(u);
}
int LCA(int u, int v)
{
    if(dep[u]< dep[v]) swap(u, v);
    for(int i = 20; i>= 0; i--)
    {
        int k = dp[i][u];
        if(dep[k]>= dep[v]) u = k;
    }
    if(u == v) return u;
    for(int i = 20; i>= 0; i--)
    {
        int a = dp[i][u], b = dp[i][v];
        if(a == b) continue;
        u = a; v = b;
    }
    return dp[0][u];
}
int main()
{
    //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
    int n, m; cin >> n >> m;
    for(int i = 1; i<= m; i++)
    {
        scanf("%d %d", &e[i].X, &e[i].Y);
        if(e[i].X == e[i].Y) continue;
        adj[e[i].X].pb(ii(e[i].Y, i));
        adj[e[i].Y].pb(ii(e[i].X, i));
    }
    for(int i = 1; i<= n; i++) if(!num[i]) dfs(i, 0);
    //for(int i = 1; i<= m; i++) printf("%d ", isB[i]); printf("\n");
    memset(num, 0, sizeof num);
    cnt = 0;
    for(int i = 1; i<= n; i++) if(!bcc[i]){ cnt++; play(i); }
    //for(int i = 1; i<= n; i++) printf("%d ", bcc[i]); printf("\n");
    for(int i = 1; i<= m; i++)
    {
        if(isB[i])
        {
            int u = e[i].X, v = e[i].Y;
            //printf("(%d, %d) is (%d, %d)\n", u, v, bcc[u], bcc[v]);
            tree[bcc[u]].pb(ii(bcc[v], i));
            tree[bcc[v]].pb(ii(bcc[u], i));
        }
    }
    for(int i = 1; i<= cnt; i++) if(!dep[i]) { dep[i]++; dfsT(i, 0); }
    for(int i = 1; i<= 20; i++)
    {
        for(int j = 1; j<= cnt; j++) dp[i][j] = dp[i-1][dp[i-1][j]];
    }
    int p; cin >> p;
    while(p--)
    {
        int a, b; cin >> a >> b;
        a = bcc[a], b = bcc[b];
        if(a == b) continue;
        sw[a]++; sw[b]--;
    }
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        int p = dp[0][u];
        sw[p] += sw[u];
        chil[p]--;
        if(p && chil[p] == 0) Q.push(p);
        if(sw[u]> 0)
        {
            int id = link[u];
            if(bcc[e[id].X] == u) ans[id] = 1;
            else ans[id] = -1;
        }
        else if(sw[u]< 0)
        {
            int id = link[u];
            if(bcc[e[id].X] == u) ans[id] = -1;
            else ans[id] = 1;
        }
    }
    for(int i = 1; i<= m; i++)
    {
        if(ans[i] == 1) printf("R");
        else if(ans[i] == -1) printf("L");
        else printf("B");
    }
    printf("\n");
}

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

oneway.cpp: In function 'int main()':
oneway.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &e[i].X, &e[i].Y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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