oj.uz

Submission #1115561

# Submission time Handle Problem Language Result Execution time Memory
1115561 2024-11-20T15:58:25 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 180 ms 91732 KB 
#include <bits/stdc++.h>

using namespace std;

#define TASK "oneway"
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }

using ii = pair<int, int>;
#define fi first
#define se second

const int N = (int)1e6 + 7;
int n, m, q;
vector<ii> adj[N];
vector<int> G[N], unUsed;
ii edge[N];
int isLeft[N], isRight[N], status[N]; // 1 B, 2 L, 3 R
int group[N];
ii way[N];

void Read()
{
    cin >> n >> m;
    REP(i, m)
    {
        int u, v;
        cin >> u >> v;
        edge[i] = {u, v};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    cin >> q;
    REP(i, q)
        cin >> way[i].fi >> way[i].se;
}

int low[N], num[N], timeVis = 0, numSCC = 0;

stack<int> st;

void Tarjan(int u, int p = -1)
{
    low[u] = num[u] = ++timeVis;
    st.push(u);
    for(auto [v, id] : adj[u])
    {
        if(id == p)
            continue;
        if(low[v])
            minimize(low[u], num[v]);
        else
        {
            Tarjan(v, id);
            minimize(low[u], low[v]);
        }
    }
    if(low[u] == num[u])
    {
        int v;
        group[u] = ++numSCC;
        do
        {
            v = st.top();
            st.pop();
            group[v] = numSCC;
        } while(v != u);
    }

}

const int LOG = 31 - __builtin_clz(N);
int par[N][LOG + 3], h[N];
void LCA_Precompute(int u, int p = -1)
{
    for(auto v : G[u])
    {
        if(v == p)
            continue;
        par[v][0] = u;
        h[v] = h[u] + 1;
        REP(i, LOG)
            par[v][i] = par[par[v][i - 1]][i - 1];
        LCA_Precompute(v, u);
    }
}

int LCA(int u, int v)
{
    if(h[u] != h[v])
    {
        if(h[u] < h[v]) swap(u, v);
        int diff = h[u] - h[v];
        FOR(i, 0, LOG)
            if(diff >> i & 1) u = par[u][i];
    }
    if(u == v) return u;
    FORD(i, LOG, 0)
    {
        if(par[u][i] == par[v][i])
            continue;
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}

int BinaryLifting(int u, int diff)
{
    FOR(i, 0, LOG)
    {
        if(diff >> i & 1) u = par[u][i];
    }
    return u;
}

void DFS(int u, int p = -1)
{
    for(auto v : G[u])
    {
        if(v == p)
            continue;
        DFS(v, u);
        isLeft[u] += isLeft[v];
        isRight[u] += isRight[v];
    }
}

void Solve()
{
    vector<int> root;
    REP(i, n)
    {
        if(!group[i])
        {
            Tarjan(i);
            root.push_back(group[i]);
        }
    }
    map<ii, int> exist;
    REP(i, m)
    {
        auto [u, v] = edge[i];
        u = group[u];
        v = group[v];
        if(u == v) status[i] = 1;
        else
        {
            unUsed.push_back(i);
            if(u > v) swap(u, v);
            if(exist.find({u, v}) != exist.end())
            {
                status[exist[{u, v}]] = 1;
                continue;
            }
            exist[{u, v}] = i;
            G[u].push_back(v);
            G[v].push_back(u);
        }
    }
//    return;
    for(auto node : root)
    {
        LCA_Precompute(node);
    }
    REP(i, q)
    {
        int u = group[way[i].fi];
        int v = group[way[i].se];
        int p = LCA(u, v);
        isLeft[u]++;
        isLeft[p]--;
        isRight[p]--;
        isRight[v]++;
    }
    for(auto node : root)
        DFS(node);
    for(auto i : unUsed)
    {
        auto [u, v] = edge[i];
        u = group[u];
        v = group[v];
        if(status[i]) continue;
        if(h[u] > h[v])
        {
            swap(u, v);
            if(isLeft[v] == isRight[v]) status[i] = 1;
            else if(isLeft[v] > isRight[v]) status[i] = 3;
            else status[i] = 2;
        }
        else
        {
            if(isLeft[v] == isRight[v]) status[i] = 1;
            else if(isLeft[v] > isRight[v]) status[i] = 2;
            else status[i] = 3;
        }
    }
    REP(i, m)
    {
        if(status[i] == 2) cout << 'L';
        else if(status[i] == 3) cout << 'R';
        else
            cout << 'B';
    }
}

signed main()
{
    cin.tie(0)->ios_base::sync_with_stdio(0);

//    if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
    if(fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    Read();
    Solve();

    return 0;
}
/**
5 4
1 2
2 3
1 4
4 5
2
2 1
5 3
*/

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:216:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:217:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 65616 KB Output is correct
2 Correct 11 ms 65504 KB Output is correct
3 Correct 11 ms 65500 KB Output is correct
4 Correct 12 ms 63568 KB Output is correct
5 Correct 12 ms 63568 KB Output is correct
6 Correct 13 ms 63568 KB Output is correct
7 Correct 12 ms 63568 KB Output is correct
8 Correct 12 ms 63568 KB Output is correct
9 Correct 16 ms 65520 KB Output is correct
10 Correct 12 ms 65616 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 65616 KB Output is correct
2 Correct 11 ms 65504 KB Output is correct
3 Correct 11 ms 65500 KB Output is correct
4 Correct 12 ms 63568 KB Output is correct
5 Correct 12 ms 63568 KB Output is correct
6 Correct 13 ms 63568 KB Output is correct
7 Correct 12 ms 63568 KB Output is correct
8 Correct 12 ms 63568 KB Output is correct
9 Correct 16 ms 65520 KB Output is correct
10 Correct 12 ms 65616 KB Output is correct
11 Correct 37 ms 70728 KB Output is correct
12 Correct 49 ms 71500 KB Output is correct
13 Correct 45 ms 74572 KB Output is correct
14 Correct 61 ms 75316 KB Output is correct
15 Correct 63 ms 78152 KB Output is correct
16 Correct 116 ms 88172 KB Output is correct
17 Correct 104 ms 84316 KB Output is correct
18 Correct 126 ms 88000 KB Output is correct
19 Correct 93 ms 87480 KB Output is correct
20 Correct 43 ms 71240 KB Output is correct
21 Correct 41 ms 70736 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 65616 KB Output is correct
2 Correct 11 ms 65504 KB Output is correct
3 Correct 11 ms 65500 KB Output is correct
4 Correct 12 ms 63568 KB Output is correct
5 Correct 12 ms 63568 KB Output is correct
6 Correct 13 ms 63568 KB Output is correct
7 Correct 12 ms 63568 KB Output is correct
8 Correct 12 ms 63568 KB Output is correct
9 Correct 16 ms 65520 KB Output is correct
10 Correct 12 ms 65616 KB Output is correct
11 Correct 37 ms 70728 KB Output is correct
12 Correct 49 ms 71500 KB Output is correct
13 Correct 45 ms 74572 KB Output is correct
14 Correct 61 ms 75316 KB Output is correct
15 Correct 63 ms 78152 KB Output is correct
16 Correct 116 ms 88172 KB Output is correct
17 Correct 104 ms 84316 KB Output is correct
18 Correct 126 ms 88000 KB Output is correct
19 Correct 93 ms 87480 KB Output is correct
20 Correct 43 ms 71240 KB Output is correct
21 Correct 41 ms 70736 KB Output is correct
22 Correct 141 ms 90560 KB Output is correct
23 Correct 180 ms 89128 KB Output is correct
24 Correct 153 ms 85952 KB Output is correct
25 Correct 115 ms 91732 KB Output is correct
26 Correct 135 ms 85696 KB Output is correct
27 Correct 147 ms 79656 KB Output is correct
28 Correct 36 ms 56392 KB Output is correct
29 Correct 55 ms 57728 KB Output is correct
30 Correct 54 ms 71900 KB Output is correct
31 Correct 50 ms 60232 KB Output is correct
32 Correct 73 ms 73680 KB Output is correct