제출 #914542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914542		sleepntsheep	Stone Arranging 2 (JOI23_ho_t1)	C++17	0 / 100	10 ms	33372 KiB

Main

#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];
void _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)
    {
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'char _qry(int, int, int, int)':
Main.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);
      |     ^~
Main.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);
      |                                    ^~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40