oj.uz

Submission #44655

# Submission time Handle Problem Language Result Execution time Memory
44655 2018-04-04T12:12:05 Z bogdan10bos One-Way Streets (CEOI17_oneway) C++14
100 / 100
 251 ms 57428 KB 
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<int, int> pii;

pii edge[100005];
int N, M, K;
int node[100005];
char r[100005];

namespace BiconnexGraph
{
    int h[100005], low[100005], f[100005];
    bool vis[100005], crit[100005];
    vector<int> edg[100005];

    void addEdge(int id)
    {
        int x = edge[id].first, y = edge[id].second;
        edg[x].push_back(id);
        edg[y].push_back(id);
    }

    int F(int x)
    {
        if(f[x] == x)   return x;
        return f[x] = F(f[x]);
    }

    void DFS(int nod, int id)
    {
        int fth = edge[id].first ^ edge[id].second ^ nod;
        h[nod] = h[fth] + 1;
        low[nod] = h[nod];

        for(auto e: edg[nod])
        {
            if(e == id)   continue;

            int nxt = edge[e].first ^ edge[e].second ^ nod;
            if(low[nxt] != 0)
            {
                low[nod] = min(low[nod], low[nxt]);
                continue;
            }

            DFS(nxt, e);
            low[nod] = min(low[nod], low[nxt]);

            if(low[nxt] > h[nod])
                crit[e] = 1;
        }
    }

    void unite(int x, int y)
    {
        if(F(x) == F(y))    return;
        f[F(y)] = F(x);
    }

    void uniteDFS(int nod)
    {
        if(vis[nod])    return;
        vis[nod] = 1;
        for(auto e: edg[nod])
        {
            int nxt = edge[e].first ^ edge[e].second ^ nod;
            if(!crit[e])
            {
                uniteDFS(nxt);
                unite(nod, nxt);
            }
        }
    }

    void compressGraph()
    {
        for(int i = 1; i <= N; i++)
            if(!low[i])
                DFS(i, 0);

        for(int i = 1; i <= N; i++) f[i] = i;
        for(int i = 1; i <= N; i++) uniteDFS(i);

        for(int i = 1; i <= N; i++) node[i] = F(i);
    }
}

namespace TreeGraph
{
    vector<int> edg[100005];
    int E, eul[100005], h[100005], f[100005], lg2[200005], up[2][100005], upedge[100005], rmq[19][200005];
    char r[100005];
    bool vis[100005];

    void addEdge(int id)
    {
        int x = node[ edge[id].first ], y = node[ edge[id].second ];
        edge[id].first = x, edge[id].second = y;
        edg[x].push_back(id);
        edg[y].push_back(id);
    }

    void DFS(int nod, int fth)
    {
        vis[nod] = 1;
        f[nod] = fth;
        h[nod] = h[fth] + 1;
        rmq[0][++E] = nod;
        eul[nod] = E;
        up[0][nod] = up[1][nod] = nod;
        for(auto e: edg[nod])
        {
            int nxt = edge[e].first ^ edge[e].second ^ nod;
            if(nxt == fth)  continue;

            upedge[nxt] = e;
            DFS(nxt, nod);
            rmq[0][++E] = nod;
        }
    }

    int minh(int a, int b)
    {
        if(h[a] < h[b]) return a;
        return b;
    }

    int LCA(int a, int b)
    {
        int pa = eul[a], pb = eul[b];
        if(pa > pb) swap(pa, pb);
        int pw = lg2[pb - pa + 1];
        return minh(rmq[pw][pa], rmq[pw][pb - (1 << pw) + 1]);
    }

    void pre()
    {
        for(int i = 1; i <= N; i++)
            if(node[i] == i && !vis[i])
                DFS(i, 0);

        for(int i = 2; i <= E; i++)
        {
            lg2[i] = lg2[i - 1];
            if( (2 << lg2[i]) == i )    lg2[i]++;
        }
        for(int i = 1; (1 << i) <= E; i++)
            for(int j = 1; j + (1 << i) - 1 <= E; j++)
                rmq[i][j] = minh(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
    }

    int UP(int dir, int x)
    {
        if(up[dir][x] == x) return x;
        return up[dir][x] = UP(dir, up[dir][x]);
    }

    void go(int x, int y, int dir)
    {
        if(h[x] <= h[y])  return;
        if(UP(dir, x) == x)
        {
            up[dir][x] = UP(dir, f[x]);
            pii e = (dir == 0 ? make_pair(x, f[x]) : make_pair(f[x], x));
            r[ upedge[x] ] = (e == edge[ upedge[x] ] ? 'R' : 'L');
        }
        go(UP(dir, x), y, dir);
    }

    void go(int x, int y)
    {
        int lca = LCA(x, y);
        go(x, lca, 0);
        go(y, lca, 1);
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        edge[i] = {x, y};
        BiconnexGraph::addEdge(i);
    }

    BiconnexGraph::compressGraph();

    for(int i = 1; i <= M; i++)
        if(BiconnexGraph::crit[i])
        {
            int x = node[ edge[i].first ];
            int y = node[ edge[i].second ];
            TreeGraph::addEdge(i);
        }
    TreeGraph::pre();

    scanf("%d", &K);
    for(int i = 1; i <= K; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if(node[x] == node[y])    continue;

        x = node[x]; y = node[y];
        TreeGraph::go(x, y);
    }

    for(int i = 1; i <= M; i++)
    {
        if(!BiconnexGraph::crit[i]) r[i] = 'B';
        else if(TreeGraph::r[i]) r[i] = TreeGraph::r[i];
        else r[i] = 'B';
    }
    printf("%s\n", r + 1);

    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:203:17: warning: unused variable 'x' [-Wunused-variable]
             int x = node[ edge[i].first ];
                 ^
oneway.cpp:204:17: warning: unused variable 'y' [-Wunused-variable]
             int y = node[ edge[i].second ];
                 ^
oneway.cpp:189: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:193: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:209:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &K);
     ~~~~~^~~~~~~~~~
oneway.cpp:213: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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5300 KB Output is correct
4 Correct 6 ms 5436 KB Output is correct
5 Correct 6 ms 5460 KB Output is correct
6 Correct 6 ms 5460 KB Output is correct
7 Correct 6 ms 5660 KB Output is correct
8 Correct 6 ms 5660 KB Output is correct
9 Correct 6 ms 5660 KB Output is correct
10 Correct 6 ms 5660 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5300 KB Output is correct
4 Correct 6 ms 5436 KB Output is correct
5 Correct 6 ms 5460 KB Output is correct
6 Correct 6 ms 5460 KB Output is correct
7 Correct 6 ms 5660 KB Output is correct
8 Correct 6 ms 5660 KB Output is correct
9 Correct 6 ms 5660 KB Output is correct
10 Correct 6 ms 5660 KB Output is correct
11 Correct 69 ms 10512 KB Output is correct
12 Correct 80 ms 13488 KB Output is correct
13 Correct 171 ms 16768 KB Output is correct
14 Correct 159 ms 22808 KB Output is correct
15 Correct 143 ms 25960 KB Output is correct
16 Correct 161 ms 37792 KB Output is correct
17 Correct 212 ms 40500 KB Output is correct
18 Correct 167 ms 40500 KB Output is correct
19 Correct 192 ms 43848 KB Output is correct
20 Correct 118 ms 43848 KB Output is correct
21 Correct 83 ms 43848 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5300 KB Output is correct
4 Correct 6 ms 5436 KB Output is correct
5 Correct 6 ms 5460 KB Output is correct
6 Correct 6 ms 5460 KB Output is correct
7 Correct 6 ms 5660 KB Output is correct
8 Correct 6 ms 5660 KB Output is correct
9 Correct 6 ms 5660 KB Output is correct
10 Correct 6 ms 5660 KB Output is correct
11 Correct 69 ms 10512 KB Output is correct
12 Correct 80 ms 13488 KB Output is correct
13 Correct 171 ms 16768 KB Output is correct
14 Correct 159 ms 22808 KB Output is correct
15 Correct 143 ms 25960 KB Output is correct
16 Correct 161 ms 37792 KB Output is correct
17 Correct 212 ms 40500 KB Output is correct
18 Correct 167 ms 40500 KB Output is correct
19 Correct 192 ms 43848 KB Output is correct
20 Correct 118 ms 43848 KB Output is correct
21 Correct 83 ms 43848 KB Output is correct
22 Correct 228 ms 47268 KB Output is correct
23 Correct 233 ms 48036 KB Output is correct
24 Correct 251 ms 50412 KB Output is correct
25 Correct 231 ms 57428 KB Output is correct
26 Correct 224 ms 57428 KB Output is correct
27 Correct 242 ms 57428 KB Output is correct
28 Correct 53 ms 57428 KB Output is correct
29 Correct 116 ms 57428 KB Output is correct
30 Correct 116 ms 57428 KB Output is correct
31 Correct 127 ms 57428 KB Output is correct
32 Correct 155 ms 57428 KB Output is correct