oj.uz

Submission #584196

# Submission time Handle Problem Language Result Execution time Memory
584196 2022-06-27T02:13:06 Z nohaxjustsoflo One-Way Streets (CEOI17_oneway) C++17
100 / 100
 217 ms 35680 KB 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
//mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 2e5+5;
const int mod = 998244353;
const int mxlogN = 20;
const int mxK = 26;
const ll inf = 1e9;

struct edge
{
    int u, v, root; bool cut; int way;
    int other(int i)
    {
        return i^u^v;
    }
};
edge es[mxN];
int vis[mxN],lowlink[mxN],_time[mxN],_timer;
vector<int> adj[mxN];
void dfs(int i, int p=-1) ///parent edge
{
    lowlink[i]=_time[i]=_timer++;
    vis[i]=1;
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(e==p||vis[j]==2) continue;
        if(vis[j]) lowlink[i]=min(lowlink[i],_time[j]);
        else
        {
            dfs(j,e);
            lowlink[i]=min(lowlink[i],lowlink[j]);
            if(lowlink[j]>_time[i]) es[e].cut=1;
        }
    }
    vis[i]=2;
}
int sz=0;
int root[mxN];
void dfs2(int i, int r)
{
    vis[i]=1;
    root[i]=r;
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(es[e].cut||vis[j]) continue;
        dfs2(j,r);
    }
}
vector<int> adjc[mxN];
int up[mxlogN][mxN], down[mxN], where[mxN], pe[mxN];
void dfs3(int i, int p=-1, int d=0)
{
    if(~p) up[0][i]=es[p].other(i);
    else up[0][i]=i;
    pe[i]=p;
    vis[i]=1;
    down[i]=d;
    where[i]=i;
    for(int j=1; j<mxlogN; j++) up[j][i]=up[j-1][up[j-1][i]];
    for(int e:adjc[i]) if(e!=p) dfs3(es[e].other(i),e,d+1);
}
int goup(int i, int k)
{
    if(!k) return i;
    for(int j=mxlogN-1; j>=0; j--)
    {
        if(k>(1<<j))
        {
            k-=1<<j;
            i=up[j][i];
        }
    }
    return up[0][i];
}
int find_lca(int i, int j)
{
    if(down[i]<down[j]) swap(i,j);
    i = goup(i,down[i]-down[j]);
    if(i==j) return i;
    for(int k=mxlogN-1; k>=0; k--)
    {
        if(up[k][i]!=up[k][j])
        {
            i=up[k][i], j=up[k][j];
        }
    }
    return up[0][i];
}
void setup(int n, int m)
{
    for(int i=0; i<n; i++) if(!vis[i]) dfs(i);
    for(int i=0; i<n; i++) vis[i]=0;
    for(int i=0; i<n; i++) if(!vis[i]) dfs2(i,sz++);
    for(int i=0; i<m; i++)
    {
        if(es[i].cut)
        {
            int u=root[es[i].u], v=root[es[i].v];
            es[i].u=u, es[i].v=v;
            adjc[u].push_back(i);
            adjc[v].push_back(i);
        }
    }
    for(int i=0; i<sz; i++) vis[i]=0;
    for(int i=0; i<sz; i++) if(!vis[i]) dfs3(i);
}
void clear_all()
{
    ///clear
}
int get(int i)
{
    if(!~pe[where[i]]) return where[i];
    if(~es[pe[where[i]]].way) where[i]=get(up[0][where[i]]);
    return where[i];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        int u,v; cin >> u >> v; u--, v--;
        es[i]={u,v};
        es[i].cut=0;
        es[i].root=-1;
        es[i].way=-1;
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    setup(n,m);
    int p; cin >> p;
    while(p--)
    {
        int x, y; cin >> x >> y; x--, y--;
        x=root[x], y=root[y];
        int lca=find_lca(x,y);
        while(1)
        {
            x=get(x);
            if(down[x]<=down[lca]) break;
            if(es[pe[x]].u==x) es[pe[x]].way=0;
            else es[pe[x]].way=1;
        }
        while(1)
        {
            y=get(y);
            if(down[y]<=down[lca]) break;
            if(es[pe[y]].v==y) es[pe[y]].way=0;
            else es[pe[y]].way=1;
        }
    }
    for(int i=0; i<m; i++)
    {
        if(!~es[i].way) cout << "B";
        else if(es[i].way) cout << "L";
        else cout << "R";
    }
    cout << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 6 ms 10000 KB Output is correct
5 Correct 6 ms 10068 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 9996 KB Output is correct
9 Correct 6 ms 9872 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 6 ms 10000 KB Output is correct
5 Correct 6 ms 10068 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 9996 KB Output is correct
9 Correct 6 ms 9872 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 42 ms 16016 KB Output is correct
12 Correct 47 ms 17036 KB Output is correct
13 Correct 63 ms 18700 KB Output is correct
14 Correct 74 ms 22332 KB Output is correct
15 Correct 76 ms 23764 KB Output is correct
16 Correct 117 ms 29996 KB Output is correct
17 Correct 123 ms 31548 KB Output is correct
18 Correct 130 ms 30036 KB Output is correct
19 Correct 97 ms 32740 KB Output is correct
20 Correct 48 ms 17032 KB Output is correct
21 Correct 44 ms 16764 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 6 ms 10000 KB Output is correct
5 Correct 6 ms 10068 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 9996 KB Output is correct
9 Correct 6 ms 9872 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 42 ms 16016 KB Output is correct
12 Correct 47 ms 17036 KB Output is correct
13 Correct 63 ms 18700 KB Output is correct
14 Correct 74 ms 22332 KB Output is correct
15 Correct 76 ms 23764 KB Output is correct
16 Correct 117 ms 29996 KB Output is correct
17 Correct 123 ms 31548 KB Output is correct
18 Correct 130 ms 30036 KB Output is correct
19 Correct 97 ms 32740 KB Output is correct
20 Correct 48 ms 17032 KB Output is correct
21 Correct 44 ms 16764 KB Output is correct
22 Correct 217 ms 32672 KB Output is correct
23 Correct 195 ms 31048 KB Output is correct
24 Correct 171 ms 31152 KB Output is correct
25 Correct 184 ms 35680 KB Output is correct
26 Correct 210 ms 32272 KB Output is correct
27 Correct 179 ms 31216 KB Output is correct
28 Correct 32 ms 14224 KB Output is correct
29 Correct 66 ms 17664 KB Output is correct
30 Correct 71 ms 17868 KB Output is correct
31 Correct 74 ms 18124 KB Output is correct
32 Correct 91 ms 23884 KB Output is correct