oj.uz

Submission #222013

# Submission time Handle Problem Language Result Execution time Memory
222013 2020-04-11T19:59:49 Z MKopchev One-Way Streets (CEOI17_oneway) C++14
100 / 100
 163 ms 35296 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={};

    noted={};

    dfs(start,0);
    /*
    cout<<component.size()<<" -> ";for(auto k:component)cout<<k<<" ";cout<<endl;

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

    //for(int i=1;i<=n;i++)cout<<i<<" -> "<<root(i)<<endl;

    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)});
                //cout<<"go "<<root(u)<<" "<<root(k)<<endl;
            }
        }

    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)
    {
        w.first.first=root(w.first.first);
        w.first.second=root(w.first.second);

        int deeper=w.first.first;
        if(depth[deeper]<depth[w.first.second])deeper=w.first.second;

        //cout<<w.first.first<<" "<<w.first.second<<" -> "<<deeper<<" , "<<w.second<<endl;

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

        if(sum[deeper]&&deeper!=w.first.first)output[w.second]='R'-output[w.second]+'L';
    }
}
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:179: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:186: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:193:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
oneway.cpp:196: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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 12 ms 7552 KB Output is correct
4 Correct 11 ms 7808 KB Output is correct
5 Correct 10 ms 7808 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 9 ms 7680 KB Output is correct
8 Correct 10 ms 7708 KB Output is correct
9 Correct 9 ms 7552 KB Output is correct
10 Correct 9 ms 7680 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 12 ms 7552 KB Output is correct
4 Correct 11 ms 7808 KB Output is correct
5 Correct 10 ms 7808 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 9 ms 7680 KB Output is correct
8 Correct 10 ms 7708 KB Output is correct
9 Correct 9 ms 7552 KB Output is correct
10 Correct 9 ms 7680 KB Output is correct
11 Correct 64 ms 14200 KB Output is correct
12 Correct 77 ms 16376 KB Output is correct
13 Correct 84 ms 19184 KB Output is correct
14 Correct 101 ms 23156 KB Output is correct
15 Correct 122 ms 24432 KB Output is correct
16 Correct 130 ms 27624 KB Output is correct
17 Correct 111 ms 28628 KB Output is correct
18 Correct 117 ms 27696 KB Output is correct
19 Correct 110 ms 29540 KB Output is correct
20 Correct 76 ms 17272 KB Output is correct
21 Correct 77 ms 17656 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 12 ms 7552 KB Output is correct
4 Correct 11 ms 7808 KB Output is correct
5 Correct 10 ms 7808 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 9 ms 7680 KB Output is correct
8 Correct 10 ms 7708 KB Output is correct
9 Correct 9 ms 7552 KB Output is correct
10 Correct 9 ms 7680 KB Output is correct
11 Correct 64 ms 14200 KB Output is correct
12 Correct 77 ms 16376 KB Output is correct
13 Correct 84 ms 19184 KB Output is correct
14 Correct 101 ms 23156 KB Output is correct
15 Correct 122 ms 24432 KB Output is correct
16 Correct 130 ms 27624 KB Output is correct
17 Correct 111 ms 28628 KB Output is correct
18 Correct 117 ms 27696 KB Output is correct
19 Correct 110 ms 29540 KB Output is correct
20 Correct 76 ms 17272 KB Output is correct
21 Correct 77 ms 17656 KB Output is correct
22 Correct 154 ms 32992 KB Output is correct
23 Correct 153 ms 31848 KB Output is correct
24 Correct 158 ms 31980 KB Output is correct
25 Correct 151 ms 35296 KB Output is correct
26 Correct 159 ms 32748 KB Output is correct
27 Correct 163 ms 31852 KB Output is correct
28 Correct 59 ms 11000 KB Output is correct
29 Correct 117 ms 20112 KB Output is correct
30 Correct 124 ms 20844 KB Output is correct
31 Correct 120 ms 19992 KB Output is correct
32 Correct 131 ms 25712 KB Output is correct