oj.uz

Submission #46974

# Submission time Handle Problem Language Result Execution time Memory
46974 2018-04-25T16:03:02 Z dqhungdl One-Way Streets (CEOI17_oneway) C++17
100 / 100
 336 ms 53416 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
int T,n,m,cnt=0,Time=0,Num[100005],Low[100005],In[100005],Out[100005],Pre[100005],h[100005],P[100005][20];
int sum1[100005],sum2[100005];
bool FEdge[100005];
vector<ii> Edge,gg[100005];
vector<int> g[100005];

void FindBridge(int u,int preid)
{
    Num[u]=Low[u]=++cnt;
    for(int i=0;i<gg[u].size();i++)
    {
        int v=gg[u][i].first;
        int id=gg[u][i].second;
        if(Num[v]==0)
        {
            FindBridge(v,id);
            Low[u]=min(Low[u],Low[v]);
            if(Low[v]>=Num[v])
                FEdge[id]=true;
        }
        else
        if(id!=preid)
            Low[u]=min(Low[u],Num[v]);
    }
}

void DFSComponent(int u,int kk)
{
    Pre[u]=kk;
    for(int i=0;i<gg[u].size();i++)
    {
        int v=gg[u][i].first;
        int id=gg[u][i].second;
        if(FEdge[id]==false&&Pre[v]==0)
            DFSComponent(v,kk);
    }
}

void DFSHigh(int u,int high)
{
    h[u]=high;
    In[u]=++Time;
    for(int i=0;i<g[u].size();i++)
        if(h[g[u][i]]==0)
        {
            P[g[u][i]][0]=u;
            DFSHigh(g[u][i],high+1);
        }
    Out[u]=Time;
}

int LCA(int u,int v)
{
    for(int k=17;k>=0;k--)
        if(h[P[u][k]]>=h[v])
            u=P[u][k];
        else
        if(h[P[v][k]]>=h[u])
            v=P[v][k];
    for(int k=17;k>=0;k--)
        if(P[u][k]!=P[v][k])
        {
            u=P[u][k];
            v=P[v][k];
        }
    while(u!=v)
    {
        u=P[u][0];
        v=P[v][0];
    }
    return u;
}

void SumDFS(int u,int root)
{
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=root)
        {
            SumDFS(g[u][i],u);
            sum1[u]+=sum1[g[u][i]];
            sum2[u]+=sum2[g[u][i]];
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n>>m;
    int u,v,Count=0;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        Edge.push_back(ii(u,v));
        gg[u].push_back(ii(v,i));
        gg[v].push_back(ii(u,i));
    }
    for(int i=1;i<=n;i++)
        if(Num[i]==0)
            FindBridge(i,0);
    for(int i=1;i<=n;i++)
        if(Pre[i]==0)
            DFSComponent(i,++Count);
    for(int i=0;i<Edge.size();i++)
    {
        int u=Pre[Edge[i].first];
        int v=Pre[Edge[i].second];
        if(u!=v)
        {
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    for(int i=1;i<=n;i++)
        if(h[i]==0)
            DFSHigh(i,1);
    for(int k=1;k<=17;k++)
        for(int i=1;i<=Count;i++)
            P[i][k]=P[P[i][k-1]][k-1];
    cin>>T;
    while(T--)
    {
        cin>>u>>v;
        u=Pre[u];
        v=Pre[v];
        int w=LCA(u,v);
        sum2[w]--;
        sum2[u]++;
        sum1[w]--;
        sum1[v]++;
    }
    SumDFS(1,1);
    for(int i=0;i<Edge.size();i++)
    {
        int u=Pre[Edge[i].first];
        int v=Pre[Edge[i].second];
        if(u==v)
            cout<<'B';
        else
        if((u==P[v][0]&&sum1[v]>0)||(v==P[u][0]&&sum2[u]>0))
            cout<<'R';
        else
        if((u==P[v][0]&&sum2[v]>0)||(v==P[u][0]&&sum1[u]>0))
            cout<<'L';
        else
            cout<<'B';
    }
}

Compilation message

oneway.cpp: In function 'void FindBridge(int, int)':
oneway.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gg[u].size();i++)
                 ~^~~~~~~~~~~~~
oneway.cpp: In function 'void DFSComponent(int, int)':
oneway.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gg[u].size();i++)
                 ~^~~~~~~~~~~~~
oneway.cpp: In function 'void DFSHigh(int, int)':
oneway.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp: In function 'void SumDFS(int, int)':
oneway.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:108:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<Edge.size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp:137:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<Edge.size();i++)
                 ~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 6 ms 5296 KB Output is correct
4 Correct 6 ms 5540 KB Output is correct
5 Correct 7 ms 5540 KB Output is correct
6 Correct 7 ms 5540 KB Output is correct
7 Correct 6 ms 5740 KB Output is correct
8 Correct 7 ms 5740 KB Output is correct
9 Correct 6 ms 5740 KB Output is correct
10 Correct 6 ms 5740 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 6 ms 5296 KB Output is correct
4 Correct 6 ms 5540 KB Output is correct
5 Correct 7 ms 5540 KB Output is correct
6 Correct 7 ms 5540 KB Output is correct
7 Correct 6 ms 5740 KB Output is correct
8 Correct 7 ms 5740 KB Output is correct
9 Correct 6 ms 5740 KB Output is correct
10 Correct 6 ms 5740 KB Output is correct
11 Correct 63 ms 11544 KB Output is correct
12 Correct 71 ms 13772 KB Output is correct
13 Correct 87 ms 16404 KB Output is correct
14 Correct 114 ms 21124 KB Output is correct
15 Correct 121 ms 23772 KB Output is correct
16 Correct 165 ms 31264 KB Output is correct
17 Correct 154 ms 33444 KB Output is correct
18 Correct 168 ms 33444 KB Output is correct
19 Correct 157 ms 36752 KB Output is correct
20 Correct 80 ms 36752 KB Output is correct
21 Correct 67 ms 36752 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 6 ms 5296 KB Output is correct
4 Correct 6 ms 5540 KB Output is correct
5 Correct 7 ms 5540 KB Output is correct
6 Correct 7 ms 5540 KB Output is correct
7 Correct 6 ms 5740 KB Output is correct
8 Correct 7 ms 5740 KB Output is correct
9 Correct 6 ms 5740 KB Output is correct
10 Correct 6 ms 5740 KB Output is correct
11 Correct 63 ms 11544 KB Output is correct
12 Correct 71 ms 13772 KB Output is correct
13 Correct 87 ms 16404 KB Output is correct
14 Correct 114 ms 21124 KB Output is correct
15 Correct 121 ms 23772 KB Output is correct
16 Correct 165 ms 31264 KB Output is correct
17 Correct 154 ms 33444 KB Output is correct
18 Correct 168 ms 33444 KB Output is correct
19 Correct 157 ms 36752 KB Output is correct
20 Correct 80 ms 36752 KB Output is correct
21 Correct 67 ms 36752 KB Output is correct
22 Correct 319 ms 40228 KB Output is correct
23 Correct 261 ms 41344 KB Output is correct
24 Correct 246 ms 43792 KB Output is correct
25 Correct 311 ms 49568 KB Output is correct
26 Correct 336 ms 49568 KB Output is correct
27 Correct 269 ms 50708 KB Output is correct
28 Correct 68 ms 50708 KB Output is correct
29 Correct 113 ms 50708 KB Output is correct
30 Correct 180 ms 50708 KB Output is correct
31 Correct 139 ms 50708 KB Output is correct
32 Correct 176 ms 53416 KB Output is correct