oj.uz

Submission #222007

# Submission time Handle Problem Language Result Execution time Memory
222007 2020-04-11T19:21:05 Z MKopchev One-Way Streets (CEOI17_oneway) C++14
0 / 100
 8 ms 7552 KB 
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;

int n,m;

vector< pair<int/*to*/,int/*id*/> > adj[nmax];

char output[nmax];

vector<int> forced[nmax];

int t,in[nmax],low[nmax];

vector<int> component;

bool cut[nmax];

void dfs(int node,int parent_edge)
{
    if(in[node])return;

    component.push_back(node);
    t++;
    in[node]=t;
    low[node]=t;

    for(auto k:adj[node])
        if(parent_edge!=k.second)
        {
            dfs(k.first,k.second);

            if(in[node]>in[k.first])low[node]=min(low[node],low[k.first]);
            else if(low[k.first]>in[node])cut[k.second]=1;
            else low[node]=min(low[node],low[k.first]);
        }
}

int parent[nmax];
int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}

vector< pair<int,int> > adj_real[nmax];

vector< pair<int,int> > go;

vector< pair< pair<int,int>, int> > noted;

int up[20][nmax],depth[nmax];

void dfs_lca(int node,int parent)
{
    up[0][node]=parent;
    depth[node]=depth[parent]+1;

    for(auto k:adj_real[node])
        if(k.first!=parent)dfs_lca(k.first,node);
}

int lca(int u,int v)
{
    if(depth[u]>depth[v])swap(u,v);

    for(int i=19;i>=0;i--)
        if(depth[v]-(1<<i)>=depth[u])v=up[i][v];

    if(u==v)return u;

    for(int i=19;i>=0;i--)
        if(up[i][u]!=up[i][v])u=up[i][u],v=up[i][v];

    return up[0][u];
}

int sum[nmax];

void dfs_sum(int node,int parent)
{
    for(auto k:adj_real[node])
        if(k.first!=parent)
        {
            dfs_sum(k.first,node);
            sum[node]+=sum[k.first];
        }
}
void solve(int start)
{
    go={};
    component={};

    dfs(start,0);

    /*
    for(int i=1;i<=m;i++)cout<<i<<" -> "<<cut[i]<<endl;
    cout<<"---"<<endl;
    */

    for(auto u:component)
        for(auto k:adj[u])
            if(cut[k.second]==0)parent[root(u)]=root(k.first);
            else noted.push_back({{u,k.first},k.second});

    if(noted.size()==0)return;

    for(auto k:noted)
    {
        adj_real[root(k.first.first)].push_back({root(k.first.second),k.second});
        adj_real[root(k.first.second)].push_back({root(k.first.first),k.second});
    }

    for(auto u:component)
        for(auto k:forced[u])
        {
            if(root(u)!=root(k))
            {
                go.push_back({root(u),root(k)});
            }
        }

    start=root(component[0]);

    dfs_lca(start,start);

    for(int st=1;st<20;st++)
        for(auto u:component)
            up[st][u]=up[st-1][up[st-1][u]];

    for(auto k:go)
    {
        int w=lca(k.first,k.second);

        sum[k.first]--;
        sum[w]++;

        sum[w]--;
        sum[k.second]++;
    }

    dfs_sum(start,start);

    for(auto u:component)
        for(auto k:adj_real[u])
            if(in[u]<in[k.first])
            {
                if(sum[k.first]>0)output[k.second]='L';
                else if(sum[k.first]<0)output[k.second]='R';
            }
}
int main()
{
    scanf("%i%i",&n,&m);

    for(int i=1;i<=n;i++)parent[i]=i;

    int u,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%i%i",&u,&v);

        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }

    int q;
    scanf("%i",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%i%i",&u,&v);
        forced[u].push_back(v);
    }

    for(int i=1;i<=n;i++)
        if(in[i]==0)solve(i);

    for(int i=1;i<=m;i++)
        if(output[i]==0)output[i]='B';

    for(int i=1;i<=m;i++)
        printf("%c",output[i]);
    printf("\n");


    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
oneway.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&u,&v);
         ~~~~~^~~~~~~~~~~~~~
oneway.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
oneway.cpp:173:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&u,&v);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7552 KB Output isn't correct
2 Halted 0 ms 0 KB -