oj.uz

Submission #735212

# Submission time Handle Problem Language Result Execution time Memory
735212 2023-05-03T17:36:41 Z MasterTaster One-Way Streets (CEOI17_oneway) C++14
0 / 100
 5 ms 5460 KB 
#include <bits/stdc++.h>

#define ll long long
#define MAXN 100010
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back

using namespace std;

int n, m, low[MAXN], tin[MAXN], tout[MAXN], timer, col[MAXN], logg;
vector<int> g[MAXN], gg[MAXN];
vector<pii> bridge, grane;
vector<pair<int, pii> >svi;
bool bio[MAXN];
map<pii, bool> b;
map<pii, int> dir;
int up[MAXN][25];

void dfs(int u, int p)
{
    bio[u]=true;
    tin[u]=low[u]=timer++;
    for (auto v:g[u])
    {
        if (v==p) continue;
        if (bio[v])
            low[u]=min(low[u], tin[v]);
        else
        {
            dfs(v, u);
            low[u]=min(low[u], low[v]);
            if (low[v]>tin[u]) { /*cout<<u<<" bridge "<<v<<endl;*/ bridge.pb({u, v}); b[{u, v}]=b[{v, u}]=true; }
        }
    }
}

void dfs2(int u, int c)
{
    bio[u]=true;
    col[u]=c;
    for (auto v:g[u])
    {
        if (!bio[v] && !b[{u, v}]) dfs2(v, c);
    }
}

void dfs3(int u, int p)
{
    ///cout<<u<<" dfs3 "<<timer+1<<endl;
    bio[u]=true;
    tin[u]=++timer;
    up[u][0]=p;
    for (int i=1; i<=logg; i++) up[u][i]=up[up[u][i-1]][i-1];
    for (auto v:gg[u])
        if (!bio[v])
            dfs3(v, u);
    tout[u]=++timer;
}

bool isanc(int u, int v) ///is u ancestor of v?
{
    return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}

int lca(int u, int v)
{
    ///cout<<tin[u]<<" "<<tout[u]<<" "<<tin[v]<<" "<<tout[v]<<endl;
    if (isanc(u, v)) return u;
    if (isanc(v, u)) return v;
    for (int i=logg; i>=0; i--)
    {
        if (!isanc(up[u][i], v)) u=up[u][i];
    }
    return up[u][0];
}

int main() {

    cin>>n>>m;
    for (int i=0; i<m; i++)
    {
        int u, v; cin>>u>>v;
        grane.pb({u, v});
        g[u].pb(v);
        g[v].pb(u);
    }

    for (int i=1; i<=n; i++)
    {
        if (!bio[i])
            dfs(i, -1);
    }

    for (int i=1; i<=n; i++) bio[i]=false;
    int cc=1;
    for (int i=1; i<=n; i++)
    {
        if (!bio[i]) dfs2(i, cc++);
    }

    //for (int i=1; i<=n; i++) cout<<col[i]<<" ";
    //cout<<endl;

    for (int i=0; i<bridge.size(); i++)
    {
        int u=col[bridge[i].xx], v=col[bridge[i].yy];
        ///cout<<"povezujem "<<u<<" "<<v<<endl;
        gg[u].pb(v); gg[v].pb(u);
    }
    for (int i=1; i<cc; i++) bio[i]=false;
    logg=ceil(log2(n));
    timer=0;
    for (int i=1; i<cc; i++)
    {
        if (!bio[i]) dfs3(i, i);
    }

    int pp; cin>>pp;
    while (pp--)
    {
        int x, y;
        cin>>x>>y;
        x=col[x];
        y=col[y];
        int xy=lca(x, y);
        svi.pb({tin[xy], {x, y}});
    }
    sort(svi.begin(), svi.end());
    for (auto par:svi)
    {
        int x=par.yy.xx; int y=par.yy.yy;
        if (x==y) continue;
        int xy=lca(x, y);
        //cout<<x<<" "<<y<<" "<<xy<<endl;
        while (x!=xy)
        {
            int p=up[x][0];
            if (dir[{x, p}]) break;
            //cout<<x<<" xp "<<p<<endl;
            dir[{x, p}]=1;
            dir[{p, x}]=2;
            x=p;
        }
        while (y!=xy)
        {
            int p=up[y][0];
            if (dir[{y, p}]) break;
            //cout<<y<<" yp "<<p<<endl;
            dir[{y, p}]=2;
            dir[{p, y}]=1;
            y=p;
        }
    }

    for (int i=0; i<m; i++)
    {
        int u, v; u=grane[i].xx; v=grane[i].yy;
        if (!b[{u, v}]) { cout<<'B'; continue; }
        u=col[u]; v=col[v];
        //cout<<u<<" uv "<<v<<endl;
        if (dir[{u, v}]==1) { cout<<'R'; }
        else if (dir[{u, v}]==2) { cout<<'L'; }
        else { cout<<'B'; }
    }
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i=0; i<bridge.size(); i++)
      |                   ~^~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5124 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 5 ms 5408 KB Output is correct
8 Correct 5 ms 5404 KB Output is correct
9 Incorrect 3 ms 5076 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5124 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 5 ms 5408 KB Output is correct
8 Correct 5 ms 5404 KB Output is correct
9 Incorrect 3 ms 5076 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5124 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 5 ms 5408 KB Output is correct
8 Correct 5 ms 5404 KB Output is correct
9 Incorrect 3 ms 5076 KB Output isn't correct
10 Halted 0 ms 0 KB -