oj.uz

답안 #914513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914513 2024-01-22T09:51:20 Z sleepntsheep One-Way Streets (CEOI17_oneway) C++17
0 / 100
 18 ms 33624 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, eid] : 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);
            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);
    _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);
    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;

    assert(Trees == 1);

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

    for (int i = 0; i < twoedgecc; ++i)
        if (hv[i] != -1)
            hld(i, i, 0);

    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 = 1; i < twoedgecc; ++i)
    {
        //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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 33624 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 33624 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 33624 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -