oj.uz

Submission #657002

# Submission time Handle Problem Language Result Execution time Memory
657002 2022-11-08T17:07:34 Z benjaminkleyn One-Way Streets (CEOI17_oneway) C++17
0 / 100
 7 ms 12120 KB 
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,fma")
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     
    const int max_n = 100001;
     
    int n, m, p;
    vector<int> g[max_n];
    bool vis[max_n] = {false};
    int ti[max_n] = {0}, lo[max_n], timer = 0;
    int a[max_n], b[max_n];
     
    char dir[max_n];
    int cmp[max_n], cnt = 0;
    stack<int> s;
    void dfs1(int u, int p = -1)
    {
        vis[u] = true;
        ti[u] = lo[u] = timer++;
        s.push(u);
        for (int i : g[u])
            if (i != p)
            {
                int v = a[i] ^ b[i] ^ u;
     
                if (vis[v])
                    lo[u] = min(lo[u], ti[v]);
                else
                {
                    dfs1(v, i);
                    lo[u] = min(lo[u], lo[v]);
                }
            }
     
        if (ti[u] == lo[u])
        {
            while (s.top() != u)
            {
                cmp[s.top()] = cnt;
                s.pop();
            }
            cmp[u] = cnt++;
            s.pop();
        }
    }
     
    vector<int> G[max_n], goal[max_n];
    set<int> sad[max_n];
    void dfs2(int u, int p = -1)
    {
        vis[u] = true;
        for (int i : G[u])
            if (i != p)
            {
                int v = cmp[a[i]] ^ cmp[b[i]] ^ u;
                dfs2(v, i);
     
                for (int node : sad[v])
                    if (sad[u].find(-node) != sad[u].end())
                        sad[u].erase(-node);
                    else
                        sad[u].insert(node);
     
                sad[v].clear();
            }
     
        for (int y : goal[u])
            if (sad[u].find(-y) != sad[u].end())
                sad[u].erase(-y);
            else
                sad[u].insert(y);
     
        if (p == -1)
            return;
     
        if (sad[u].size() == 0)
            dir[p] = 'B';
        else if (*sad[u].begin() > 0)
            dir[p] = (cmp[a[p]] == u ? 'L' : 'R');
        else
            dir[p] = (cmp[b[p]] == u ? 'R' : 'L');
     
    }
     
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
     
        cin >> n >> m;
        for (int i = 0; i < m; i++)
        {
            dir[i] = 'B';
            cin >> a[i] >> b[i];
            a[i]--, b[i]--;
            g[a[i]].push_back(i);
            g[b[i]].push_back(i);
        }
     
        for (int u = 0; u < n; u++)
        {
            if (!vis[u])
                dfs1(u);
            vis[u] = false;
     
            for (int i : g[u])
            {
                int v = a[i] ^ b[i] ^ u;
                if (cmp[v] != cmp[u])
                    G[cmp[u]].push_back(i);
                else
                    dir[i] = 'B';
            }
        }
     
        cin >> p;
        for (int i = 0, x, y; i < p; i++)
        {
            cin >> x >> y;
            x--, y--;
            goal[cmp[x]].push_back(i);
            goal[cmp[y]].push_back(-i);
        }
     
        memset(vis, false, sizeof vis);
        for (int i = 0; i < cnt; i++)
            if (!vis[i])
                dfs2(i);
     
        for (int i = 0; i < m; i++)
            cout << dir[i];
        cout << '\n';
     
        return 0;
    }

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12120 KB Output isn't correct
2 Halted 0 ms 0 KB -