oj.uz

Submission #222010

# Submission time Handle Problem Language Result Execution time Memory
222010 2020-04-11T19:38:21 Z MKopchev One-Way Streets (CEOI17_oneway) C++14
0 / 100
 9 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(abs(parent_edge)!=abs(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[abs(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)
{
    //cout<<"dfs_sum "<<node<<" "<<parent<<endl;

    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(k.second>0&&cut[k.second]==0)parent[root(u)]=root(k.first);
            else if(k.second>0)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});

        //cout<<root(k.first.first)<<" with "<<root(k.first.second)<<endl;
    }

    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]);

    //cout<<"start= "<<start<<endl;

    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]++;
    }

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

    dfs_sum(start,start);

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

    for(auto w:noted)
    {
        int deeper=w.first.first;
        if(depth[deeper]<depth[w.first.second])deeper=w.first.second;

        if(sum[deeper]>0)output[w.second]='L';
        else if(sum[deeper]<0)output[w.second]='R';

        if(deeper!=w.first.first)output[w.second]='L'+'R'-output[w.second];
    }
}
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:169: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:176: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:183:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
oneway.cpp:186: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 9 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 9 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 9 ms 7552 KB Output isn't correct
2 Halted 0 ms 0 KB -