oj.uz

답안 #914538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914538 2024-01-22T10:16:51 Z sleepntsheep One-Way Streets (CEOI17_oneway) C++17
100 / 100
 335 ms 47588 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]);
    }

    if (tin[u] == low[u])
    {
        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, _);
}

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);
}

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

void updup(int u, int a, int d)
{
    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';

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

    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);
    }

    //_build(0, 0, ctimer);
    for (int i = 0; i < twoedgecc; ++i)
    {
        if (aux[i] == 0) continue;
        ans[abs(aux[i])] = final_2_last[ci[i]];
        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:120:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  120 |     if(p<=m)return _qry(vl,l,m,p); return _qry(vr,m+1,r,p);
      |     ^~
oneway.cpp:120:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  120 |     if(p<=m)return _qry(vl,l,m,p); return _qry(vr,m+1,r,p);
      |                                    ^~~~~~
oneway.cpp: In function 'char _build(int, int, int)':
oneway.cpp:135:1: warning: no return statement in function returning non-void [-Wreturn-type]
  135 | }
      | ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 7 ms 33292 KB Output is correct
3 Correct 8 ms 33372 KB Output is correct
4 Correct 8 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 8 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 9 ms 33624 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 7 ms 33292 KB Output is correct
3 Correct 8 ms 33372 KB Output is correct
4 Correct 8 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 8 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 9 ms 33624 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 36 ms 37356 KB Output is correct
12 Correct 33 ms 38224 KB Output is correct
13 Correct 37 ms 38740 KB Output is correct
14 Correct 44 ms 39756 KB Output is correct
15 Correct 49 ms 39632 KB Output is correct
16 Correct 104 ms 39948 KB Output is correct
17 Correct 68 ms 42576 KB Output is correct
18 Correct 61 ms 39768 KB Output is correct
19 Correct 69 ms 44472 KB Output is correct
20 Correct 44 ms 37712 KB Output is correct
21 Correct 33 ms 37204 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 7 ms 33292 KB Output is correct
3 Correct 8 ms 33372 KB Output is correct
4 Correct 8 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 8 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 9 ms 33624 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 36 ms 37356 KB Output is correct
12 Correct 33 ms 38224 KB Output is correct
13 Correct 37 ms 38740 KB Output is correct
14 Correct 44 ms 39756 KB Output is correct
15 Correct 49 ms 39632 KB Output is correct
16 Correct 104 ms 39948 KB Output is correct
17 Correct 68 ms 42576 KB Output is correct
18 Correct 61 ms 39768 KB Output is correct
19 Correct 69 ms 44472 KB Output is correct
20 Correct 44 ms 37712 KB Output is correct
21 Correct 33 ms 37204 KB Output is correct
22 Correct 241 ms 42472 KB Output is correct
23 Correct 335 ms 40488 KB Output is correct
24 Correct 303 ms 39836 KB Output is correct
25 Correct 212 ms 47588 KB Output is correct
26 Correct 254 ms 42068 KB Output is correct
27 Correct 311 ms 40500 KB Output is correct
28 Correct 26 ms 35416 KB Output is correct
29 Correct 58 ms 37180 KB Output is correct
30 Correct 86 ms 37204 KB Output is correct
31 Correct 49 ms 37712 KB Output is correct
32 Correct 155 ms 40860 KB Output is correct