oj.uz

Submission #92956

# Submission time Handle Problem Language Result Execution time Memory
92956 2019-01-06T09:02:54 Z Kastanda One-Way Streets (CEOI17_oneway) C++11
100 / 100
 241 ms 29816 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5496 KB Output is correct
2 Correct 6 ms 5496 KB Output is correct
3 Correct 5 ms 5624 KB Output is correct
4 Correct 6 ms 5624 KB Output is correct
5 Correct 6 ms 5752 KB Output is correct
6 Correct 5 ms 5496 KB Output is correct
7 Correct 6 ms 5752 KB Output is correct
8 Correct 6 ms 5624 KB Output is correct
9 Correct 5 ms 5500 KB Output is correct
10 Correct 5 ms 5496 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5496 KB Output is correct
2 Correct 6 ms 5496 KB Output is correct
3 Correct 5 ms 5624 KB Output is correct
4 Correct 6 ms 5624 KB Output is correct
5 Correct 6 ms 5752 KB Output is correct
6 Correct 5 ms 5496 KB Output is correct
7 Correct 6 ms 5752 KB Output is correct
8 Correct 6 ms 5624 KB Output is correct
9 Correct 5 ms 5500 KB Output is correct
10 Correct 5 ms 5496 KB Output is correct
11 Correct 52 ms 10488 KB Output is correct
12 Correct 59 ms 11512 KB Output is correct
13 Correct 57 ms 12996 KB Output is correct
14 Correct 97 ms 16376 KB Output is correct
15 Correct 111 ms 17784 KB Output is correct
16 Correct 110 ms 23544 KB Output is correct
17 Correct 137 ms 24984 KB Output is correct
18 Correct 132 ms 23536 KB Output is correct
19 Correct 141 ms 26104 KB Output is correct
20 Correct 60 ms 11384 KB Output is correct
21 Correct 54 ms 11148 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5496 KB Output is correct
2 Correct 6 ms 5496 KB Output is correct
3 Correct 5 ms 5624 KB Output is correct
4 Correct 6 ms 5624 KB Output is correct
5 Correct 6 ms 5752 KB Output is correct
6 Correct 5 ms 5496 KB Output is correct
7 Correct 6 ms 5752 KB Output is correct
8 Correct 6 ms 5624 KB Output is correct
9 Correct 5 ms 5500 KB Output is correct
10 Correct 5 ms 5496 KB Output is correct
11 Correct 52 ms 10488 KB Output is correct
12 Correct 59 ms 11512 KB Output is correct
13 Correct 57 ms 12996 KB Output is correct
14 Correct 97 ms 16376 KB Output is correct
15 Correct 111 ms 17784 KB Output is correct
16 Correct 110 ms 23544 KB Output is correct
17 Correct 137 ms 24984 KB Output is correct
18 Correct 132 ms 23536 KB Output is correct
19 Correct 141 ms 26104 KB Output is correct
20 Correct 60 ms 11384 KB Output is correct
21 Correct 54 ms 11148 KB Output is correct
22 Correct 219 ms 26908 KB Output is correct
23 Correct 227 ms 25292 KB Output is correct
24 Correct 241 ms 25340 KB Output is correct
25 Correct 163 ms 29816 KB Output is correct
26 Correct 153 ms 26432 KB Output is correct
27 Correct 141 ms 25328 KB Output is correct
28 Correct 42 ms 9464 KB Output is correct
29 Correct 89 ms 13008 KB Output is correct
30 Correct 78 ms 13032 KB Output is correct
31 Correct 78 ms 13304 KB Output is correct
32 Correct 109 ms 18780 KB Output is correct