oj.uz

Submission #656994

# Submission time Handle Problem Language Result Execution time Memory
656994 2022-11-08T16:49:25 Z benjaminkleyn One-Way Streets (CEOI17_oneway) C++17
0 / 100
 7 ms 12116 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(y);
        goal[cmp[y]].push_back(-x);
    }

    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 12116 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 12116 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 12116 KB Output isn't correct
2 Halted 0 ms 0 KB -