Submission #92956

#	Time	Username	Problem	Language	Result	Execution time	Memory
92956		Kastanda	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	241 ms	29816 KiB

oneway

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 100005, LG = 18;
int n, m, q, from[N], to[N], M[N], H[N], Mn[N];
int cp, Hc[N], C[N], P[N][LG], up[N], dn[N];
int qa[N], qb[N];
char R[N];
vector < int > Adj[N], Ad[N];
void DFS(int v, int p)
{
    Mn[v] = H[v]; M[v] = 1;
    for (int &id : Adj[v])
    {
        if (id == p)
            continue;
        int u = from[id] ^ to[id] ^ v;
        if (M[u] == 2)
            continue;
        else if (M[u] == 1)
            Mn[v] = min(Mn[v], H[u]);
        else
        {
            H[u] = H[v] + 1;
            DFS(u, id);
            Mn[v] = min(Mn[v], Mn[u]);
        }
    }
    M[v] = 2;
}
void DFS2(int v, int p, int pc)
{
    C[v] = pc; M[v] = 1;
    for (int &id : Adj[v])
    {
        if (id == p)
            continue;
        int u = from[id] ^ to[id] ^ v;
        if (M[u])
            continue;
        if (Mn[u] < H[u])
            DFS2(u, id, pc);
        else
        {
            ++ cp;
            Ad[pc].pb(id);
            Ad[cp].pb(id);
            P[cp][0] = pc;
            Hc[cp] = Hc[pc] + 1;
            DFS2(u, id, cp);
        }
    }
}
void DFS3(int v, int p)
{
    M[v] = 1;
    for (int &id : Ad[v])
    {
        if (id == p)
            continue;
        int u = from[id];
        if (C[u] == v)
            u = to[id];
        DFS3(C[u], id);
        up[v] = max(up[v], up[C[u]] - 1);
        dn[v] = max(dn[v], dn[C[u]] - 1);
    }
    if (up[v] && dn[v])
        exit(1);
    if (up[v])
    {
        if (C[from[p]] == v)
            R[p] = 'R';
        else
            R[p] = 'L';
    }
    if (dn[v])
    {
        if (C[from[p]] == v)
            R[p] = 'L';
        else
            R[p] = 'R';
    }
}
inline int LCA(int v, int u)
{
    if (Hc[v] < Hc[u])
        swap(v, u);
    for (int i = 0; i < LG; i++)
        if ((Hc[v] - Hc[u]) & (1 << i))
            v = P[v][i];
    if (v == u)
        return (v);
    for (int i = LG - 1; ~i; i--)
        if (P[v][i] != P[u][i])
            v = P[v][i], u = P[u][i];
    return (P[v][0]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &from[i], &to[i]);
        Adj[from[i]].pb(i);
        Adj[to[i]].pb(i);
        R[i] = 'B';
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
        scanf("%d%d", &qa[i], &qb[i]);

    for (int i = 1; i <= n; i++)
        if (!M[i])
            DFS(i, -1);
    memset(M, 0, sizeof(M));
    for (int i = 1; i <= n; i++)
        if (!M[i])
            cp ++, DFS2(i, -1, cp);
    for (int i = 1; i < LG; i++)
        for (int v = 1; v <= cp; v ++)
            P[v][i] = P[P[v][i - 1]][i - 1];

    for (int i = 1; i <= q; i++)
    {
        int a = qa[i], b = qb[i];
        if (C[a] == C[b])
            continue;
        int lca = LCA(C[a], C[b]);
        up[C[a]] = max(up[C[a]], Hc[C[a]] - Hc[lca]);
        dn[C[b]] = max(dn[C[b]], Hc[C[b]] - Hc[lca]);
    }
    memset(M, 0, sizeof(M));
    for (int i = 1; i <= cp; i++)
        if (!M[i])
            DFS3(i, -1);

    printf("%s\n", R + 1);
    return (0);
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:101: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:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &from[i], &to[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
oneway.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &qa[i], &qb[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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