Submission #1172464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172464		HoriaHaivas	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	3092 ms	5184 KiB

oneway

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

struct muchie
{
    bool visited;
    int u;
    int ou;
    int v;
    int ov;
    int cycles;
};

struct bruh
{
    int to;
    int id;
};

muchie edge[100005];
vector<bruh> nodes[100005];
vector<bruh> children[100005];
int inedge[100005];
int h[100005];
int p[100005];
int up[17][100005];
bool visited[100005];

void dfs(int node)
{
    if (visited[node])
        return;
    visited[node]=1;
    for (auto x : nodes[node])
    {
        if (!visited[x.to])
        {
            children[node].push_back(x);
            edge[x.id].visited=1;
            inedge[x.to]=x.id;
            h[x.to]=h[node]+1;
            p[x.to]=node;
            dfs(x.to);
        }
    }
}

void pull(int node)
{
    for (auto x : children[node])
    {
        pull(x.to);
        edge[inedge[node]].cycles+=edge[x.id].cycles;
    }
}

int timer;
int tin[100005];
int tout[100005];

void dfs2(int node)
{
    timer++;
    tin[inedge[node]]=timer;
    for (auto x : children[node])
    {
        dfs2(x.to);
    }
    timer++;
    tout[inedge[node]]=timer;
}

class AIB
{
public:
    int aib[200005];
    void update(int idx, int delta)
    {
        while (idx<=timer)
        {
            aib[idx]+=delta;
            idx+=idx&(-idx);
        }
    }
    void update(int l, int r, int delta)
    {
         update(l,delta);
         update(r+1,-delta);
    }
    int query(int idx)
    {
        int ans;
        ans=0;
        while(idx>0)
        {
            ans+=aib[idx];
            idx-=idx&(-idx);
        }
        return ans;
    }
} aib;

int jump(int node, int k)
{
    int i;
    for (i=0;i<=16;i++)
    {
         if (k&(1<<i))
             node=up[i][node];
    }
    return node;
}

int lca(int a, int b)
{
    int i,k;
    if (h[a]<h[b])
        swap(a,b);
    k=h[a]-h[b];
    a=jump(a,k);
    if (a==b)
        return a;
    for (i=16;i>=0;i--)
    {
         if (up[i][a]!=up[i][b])
         {
             a=up[i][a];
             b=up[i][b];
         }
    }
    return up[0][a];
}

bool is_ancestor(int a, int b)
{
    int k;
    if (h[a]<h[b])
        swap(a,b);
    k=h[a]-h[b];
    if (jump(a,k)!=b)
        return 0;
    return 1;
}

int val[100005];

void addpath(int from, int to, int delta)
{
     while (from!=to)
     {
         val[inedge[from]]+=delta;
         from=p[from];
     }
}

void configure_path(int from, int to)
{
    if (is_ancestor(from,to))
    {
        addpath(to,from,1);
        //aib.update(tin[inedge[to]],tout[inedge[to]],1);
        //aib.update(tin[inedge[from]],tout[inedge[from]],-1);
        return;
    }
    if (is_ancestor(to,from))
    {
        addpath(from,to,-1);
        //aib.update(tin[inedge[from]],tout[inedge[from]],-1);
        //aib.update(tin[inedge[to]],tout[inedge[to]],1);
        return;
    }
    int c;
    c=lca(from,to);
    //aib.update(tin[inedge[from]],tout[inedge[from]],-1);
    //aib.update(tin[inedge[c]],tout[inedge[c]],1);
    addpath(from,c,-1);
    //aib.update(tin[inedge[to]],tout[inedge[to]],1);
    //aib.update(tin[inedge[c]],tout[inedge[c]],-1);
    addpath(to,c,1);
}

signed main()
{
    //ifstream fin("secvp.in");
    //ofstream fout("secvp.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,i,j,u,v,req;
    cin >> n >> m;
    for (i=1; i<=m; i++)
    {
        cin >> u >> v;
        nodes[u].push_back({v,i});
        nodes[v].push_back({u,i});
        edge[i].u=u;
        edge[i].ou=u;
        edge[i].v=v;
        edge[i].ov=v;
        edge[i].cycles=0;
        edge[i].visited=0;
    }
    h[1]=1;
    p[1]=1;
    dfs(1);
    for (i=1; i<=m; i++)
    {
        if (h[edge[i].u]<h[edge[i].v])
            swap(edge[i].u,edge[i].v);
        if (!edge[i].visited)
        {
            edge[i].cycles++;
            edge[inedge[edge[i].u]].cycles++;
            edge[inedge[edge[i].v]].cycles--;
        }
    }
    pull(1);
    for (i=1; i<=n; i++)
    {
        up[0][i]=p[i];
    }
    for (i=1; i<=16; i++)
    {
        for (j=1; j<=n; j++)
        {
            up[i][j]=up[i-1][up[i-1][j]];
        }
    }
    dfs2(1);
    cin >> req;
    for (i=1; i<=req; i++)
    {
        cin >> u >> v;
        configure_path(u,v);
    }
    string rez;
    rez="";
    for (i=1;i<=m;i++)
    {
         if (!edge[i].cycles)
         {
             if (val[i]>0)///sus->jos
             {
                 if (edge[i].ou==edge[i].u)
                 {
                     rez+="L";
                 }
                 else
                 {
                     rez+="R";
                 }
             }
             else if (val[i]<0) ///jos->sus
             {
                 if (edge[i].ou==edge[i].u)
                 {
                     rez+="R";
                 }
                 else
                 {
                     rez+="L";
                 }
             }
             else
             {
                 rez+="B";
             }
         }
         else
         {
            rez+="B";
         }
    }
    cout << rez;
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40