oj.uz

Submission #914524

# Submission time Handle Problem Language Result Execution time Memory
914524 2024-01-22T10:05:00 Z sleepntsheep One-Way Streets (CEOI17_oneway) C++17
100 / 100
 323 ms 49772 KB 
#include <stack>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

int n, m, p;
basic_string<pair<int, int>> g[N];

int tin[N], low[N], timer; char ans[N];
int grp[N], twoedgecc;

stack<int> sd;

void tarjan(int u, int p)
{
    tin[u] = low[u] = ++timer;
    sd.push(u);

    for (auto [v, _] : g[u])
    {
        if (v == p)
        {
            p = -1;
            continue;
        }
        if (!tin[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], tin[v]);
    }

    if (tin[u] == low[u])
    {
        //cout<<"NEWCOM "<<twoedgecc<<' '<<u<<'\n';
        int v;
        do
        {
            grp[v = sd.top()] = twoedgecc;
            sd.pop();
        }
        while (v != u);
        ++twoedgecc;
    }
}

basic_string<pair<int, int> > G[N];

int aux[N], sz[N], ch[N], ci[N], P[20][N], hv[N], hveid[N], dep[N];

void dfs(int u, int p)
{
    sz[u] = 1;
    P[0][u] = p;
    for (int j = 1; j < 18; ++j) P[j][u] = P[j-1][P[j-1][u]];
    int hvsz = -1;
    for (auto [v, _] : G[u]) if (v != p)
    {
        dep[v] = dep[u] + 1;
        dfs(v, u); sz[u] += sz[v];
        if (sz[v] > hvsz) hv[u] = v, hvsz = sz[v], hveid[u] = _;
    }
}

int ctimer;
void hld(int u, int h, int pd)
{
    ci[u] = ctimer++; ch[u] = h;
    aux[u] = pd;
    if (hv[u]) hld(hv[u], h, hveid[u]);
    for (auto [v, _] : G[u]) if (v != P[0][u] and v != hv[u]) hld(v, v, _);
    hv[u] = -1;
}

int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(v, u);
    int dt = dep[u] - dep[v];
    for(int j=18;j--;)if(dt&(1<<j))u=P[j][u];
    if(u==v)return u;
    for(int j=18;j--;)if(P[j][u]-P[j][v])u=P[j][u],v=P[j][v];
    return P[0][u];
}

char whatt[N<<1], lz[N<<1];
void _push(int v, int l, int r)
{
    if (lz[v])
    {
        whatt[v]=lz[v];
        if (l-r)
        {
            auto m=(l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
            lz[vl]=lz[vr]=lz[v];
        }
        lz[v]=0;
    }
}

void _set(int v, int l, int r,int x,int y,int k)
{
    _push(v,l,r);
    if(r<x or y<l)return;
    if(x<=l and r<=y){lz[v]=k;_push(v,l,r);return;}
    auto m=(l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
    _set(vl,l,m,x,y,k);_set(vr,m+1,r,x,y,k);
}

char _qry(int v,int l, int r, int p)
{
    _push(v,l,r);
    if(l==r)return whatt[v];
    auto m=(l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
    if(p<=m)return _qry(vl,l,m,p); return _qry(vr,m+1,r,p);
}

void updup(int u, int a, int d)
{
    //cout << "UPDUP " << u << ' ' << a << ' ' << char(d)<<'\n';
    for (; ch[u] != ch[a]; u = P[0][ch[u]])
        _set(0, 0, ctimer, ci[ch[u]], ci[u], d);
    _set(0, 0, ctimer, ci[a], ci[u], d);
}

int main()
{
    ShinLena;
    cin >> n >> m;
    for (int u, v, i = 1; i <= m; ++i)
        cin >> u >> v, g[u].push_back({v, i}), g[v].push_back({u, -i}), ans[i] = 'B';

    int Trees = 0;
    for (int i = 1; i <= n; ++i) if (!tin[i]) tarjan(i, -1), ++Trees;

    for (int u = 1; u <= n; ++u)
        for (auto [v, eid] : g[u])
            if (eid > 0 and grp[u] != grp[v])
                G[grp[u]].push_back({grp[v], eid}), G[grp[v]].push_back({grp[u], -eid});

    for (int i = 0; i < twoedgecc; ++i)
        sort(ALL(G[i])), G[i].resize(unique(ALL(G[i])) - G[i].begin());

    
    for (int i = 0; i < twoedgecc; ++i) if (!sz[i])
    {
        dfs(i, -1);
        hld(i, i, 0);
    }

    _set(0, 0, ctimer, 0, ctimer, 'B');


    cin >> p;
    for (int x, y, i = 0; i < p; ++i)
    {
        cin >> x >> y;
        if ((x = grp[x]) == (y = grp[y])) continue;
        int a = lca(x, y);
        int X = _qry(0,0,ctimer,ci[a]);
        updup(x, a, 'L');
        updup(y, a, 'R');
        _set(0,0,ctimer,ci[a],ci[a],X);
    }

    for (int i = 0; i < twoedgecc; ++i)
    {
        if (aux[i] == 0) continue;
        //cout << i << ' ' << aux[i] <<' '<<char(what[ci[i]])<<'\n';
        ans[abs(aux[i])] = _qry(0,0,ctimer,ci[i]);
        if (aux[i] < 0)
        {
            aux[i] *= -1;
            if (ans[aux[i]] == 'L') ans[aux[i]] = 'R';
            else if (ans[aux[i]] == 'R') ans[aux[i]] = 'L';
        }
    }

    cout << (ans+1);


    return 0;
}

Compilation message

oneway.cpp: In function 'char _qry(int, int, int, int)':
oneway.cpp:131:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  131 |     if(p<=m)return _qry(vl,l,m,p); return _qry(vr,m+1,r,p);
      |     ^~
oneway.cpp:131:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  131 |     if(p<=m)return _qry(vl,l,m,p); return _qry(vr,m+1,r,p);
      |                                    ^~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31064 KB Output is correct
2 Correct 7 ms 31068 KB Output is correct
3 Correct 7 ms 31184 KB Output is correct
4 Correct 8 ms 31068 KB Output is correct
5 Correct 7 ms 31156 KB Output is correct
6 Correct 8 ms 31064 KB Output is correct
7 Correct 8 ms 31068 KB Output is correct
8 Correct 10 ms 31068 KB Output is correct
9 Correct 8 ms 31064 KB Output is correct
10 Correct 8 ms 31068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31064 KB Output is correct
2 Correct 7 ms 31068 KB Output is correct
3 Correct 7 ms 31184 KB Output is correct
4 Correct 8 ms 31068 KB Output is correct
5 Correct 7 ms 31156 KB Output is correct
6 Correct 8 ms 31064 KB Output is correct
7 Correct 8 ms 31068 KB Output is correct
8 Correct 10 ms 31068 KB Output is correct
9 Correct 8 ms 31064 KB Output is correct
10 Correct 8 ms 31068 KB Output is correct
11 Correct 34 ms 36176 KB Output is correct
12 Correct 37 ms 36984 KB Output is correct
13 Correct 39 ms 37604 KB Output is correct
14 Correct 44 ms 38268 KB Output is correct
15 Correct 51 ms 40448 KB Output is correct
16 Correct 62 ms 41084 KB Output is correct
17 Correct 70 ms 43552 KB Output is correct
18 Correct 65 ms 41072 KB Output is correct
19 Correct 71 ms 45396 KB Output is correct
20 Correct 36 ms 36372 KB Output is correct
21 Correct 35 ms 36180 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31064 KB Output is correct
2 Correct 7 ms 31068 KB Output is correct
3 Correct 7 ms 31184 KB Output is correct
4 Correct 8 ms 31068 KB Output is correct
5 Correct 7 ms 31156 KB Output is correct
6 Correct 8 ms 31064 KB Output is correct
7 Correct 8 ms 31068 KB Output is correct
8 Correct 10 ms 31068 KB Output is correct
9 Correct 8 ms 31064 KB Output is correct
10 Correct 8 ms 31068 KB Output is correct
11 Correct 34 ms 36176 KB Output is correct
12 Correct 37 ms 36984 KB Output is correct
13 Correct 39 ms 37604 KB Output is correct
14 Correct 44 ms 38268 KB Output is correct
15 Correct 51 ms 40448 KB Output is correct
16 Correct 62 ms 41084 KB Output is correct
17 Correct 70 ms 43552 KB Output is correct
18 Correct 65 ms 41072 KB Output is correct
19 Correct 71 ms 45396 KB Output is correct
20 Correct 36 ms 36372 KB Output is correct
21 Correct 35 ms 36180 KB Output is correct
22 Correct 237 ms 44624 KB Output is correct
23 Correct 323 ms 42960 KB Output is correct
24 Correct 292 ms 42064 KB Output is correct
25 Correct 242 ms 49772 KB Output is correct
26 Correct 239 ms 44436 KB Output is correct
27 Correct 303 ms 42844 KB Output is correct
28 Correct 29 ms 34388 KB Output is correct
29 Correct 60 ms 37204 KB Output is correct
30 Correct 85 ms 37376 KB Output is correct
31 Correct 50 ms 37712 KB Output is correct
32 Correct 167 ms 41044 KB Output is correct