oj.uz

Submission #92322

# Submission time Handle Problem Language Result Execution time Memory
92322 2019-01-02T13:35:08 Z Bodo171 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 160 ms 25220 KB 
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
char ans[nmax];
vector<int> v[nmax],ag[nmax];
int tt[nmax],rg[nmax],dad[nmax],bc[nmax],st[nmax],lnod[nmax],rnod[nmax],l[nmax],r[nmax],low[nmax],lev[nmax],a[nmax],b[nmax],to_dad[nmax],sus[nmax],edg[nmax],marked[nmax];
int n,m,q,bcc,u,nr,i,x,y,mu;
int finds(int x)
{
    int y=x,aux;
    while(x!=tt[x])
        x=tt[x];
    while(y!=x)
    {
        aux=tt[y];
        tt[y]=x;
        y=aux;
    }
    return x;
}
void unite(int A,int B)
{
    if(rg[A]<rg[B]) swap(A,B);
    tt[B]=A;
    rg[A]+=rg[B];
}
void mark_bcc(int x)
{
    bc[st[u]]=bcc;
    for(int i=0;i<ag[st[u]].size();i++)
    {
        dad[ag[st[u]][i]]=bcc;
    }
    if(st[u]==x)
    {
        u--;
        return;
    }
    u--;
    mark_bcc(x);
}
void dfs(int x)
{
    int nod=0,mu=0;
    low[x]=n+1;lnod[x]=++nr;st[++u]=x;
    for(int i=0;i<v[x].size();i++)
    {
        mu=v[x][i];
        nod=(a[mu]^b[mu]^x);
        if(!lev[nod])
        {
            lev[nod]=lev[x]+1;
            edg[nod]=mu;
            dfs(nod);
            if(low[nod]>lev[x])
            {
                ++bcc;
                mark_bcc(nod);
                l[bcc]=lnod[nod];
                r[bcc]=rnod[nod];
                to_dad[bcc]=mu;
                ag[x].push_back(bcc);
            }
            low[x]=min(low[x],low[nod]);
        }
        else
        {
            if(mu!=edg[x])
                low[x]=min(low[x],lev[nod]);
        }
    }
    rnod[x]=nr;
}
bool cup(int A,int B)
{
    return (l[A]<=l[B]&&r[B]<=r[A]);
}
void mark(int x,int oth,int col)
{
    while(!cup(x,oth))
    {
        marked[x]=col;
        sus[finds(x)]=sus[finds(dad[x])];
        unite(finds(x),finds(dad[x]));
        x=sus[finds(x)];
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
        v[a[i]].push_back(i);
        v[b[i]].push_back(i);
    }
    for(int S=1;S<=n;S++)
        if(!lev[S])
    {
        lev[S]=1;
        dfs(S);
        if(u)
          {
              ++bcc;
              l[bcc]=lnod[st[1]];
              r[bcc]=rnod[st[1]];
              mark_bcc(st[1]);
          }
    }
    for(i=1;i<=bcc;i++)
        tt[i]=i,rg[i]=1,sus[i]=i;
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>x>>y;
        x=bc[x];y=bc[y];
        mark(x,y,1);
        mark(y,x,2);
    }
    for(i=0;i<m;i++)
        ans[i]='B';
    for(i=1;i<=bcc;i++)
        if(marked[i])
    {
        mu=to_dad[i];
        if((bc[a[mu]]==i&&marked[i]==1)||(marked[i]==2&&bc[a[mu]]!=i)) ans[mu-1]='R';
        else ans[mu-1]='L';
    }
    cout<<ans;
    return 0;
}

Compilation message

oneway.cpp: In function 'void mark_bcc(int)':
oneway.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ag[st[u]].size();i++)
                 ~^~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int)':
oneway.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].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 6 ms 5112 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 7 ms 5240 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 6 ms 5244 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 6 ms 5240 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 6 ms 5244 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 6 ms 5112 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 7 ms 5240 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 6 ms 5244 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 6 ms 5240 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 6 ms 5244 KB Output is correct
11 Correct 44 ms 10616 KB Output is correct
12 Correct 57 ms 11920 KB Output is correct
13 Correct 71 ms 13636 KB Output is correct
14 Correct 105 ms 16084 KB Output is correct
15 Correct 94 ms 16720 KB Output is correct
16 Correct 110 ms 17188 KB Output is correct
17 Correct 106 ms 20016 KB Output is correct
18 Correct 103 ms 17528 KB Output is correct
19 Correct 101 ms 21424 KB Output is correct
20 Correct 56 ms 12284 KB Output is correct
21 Correct 60 ms 11656 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 6 ms 5112 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 7 ms 5240 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 6 ms 5244 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 6 ms 5240 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 6 ms 5244 KB Output is correct
11 Correct 44 ms 10616 KB Output is correct
12 Correct 57 ms 11920 KB Output is correct
13 Correct 71 ms 13636 KB Output is correct
14 Correct 105 ms 16084 KB Output is correct
15 Correct 94 ms 16720 KB Output is correct
16 Correct 110 ms 17188 KB Output is correct
17 Correct 106 ms 20016 KB Output is correct
18 Correct 103 ms 17528 KB Output is correct
19 Correct 101 ms 21424 KB Output is correct
20 Correct 56 ms 12284 KB Output is correct
21 Correct 60 ms 11656 KB Output is correct
22 Correct 151 ms 21308 KB Output is correct
23 Correct 156 ms 19100 KB Output is correct
24 Correct 153 ms 18680 KB Output is correct
25 Correct 152 ms 25220 KB Output is correct
26 Correct 146 ms 20576 KB Output is correct
27 Correct 160 ms 19176 KB Output is correct
28 Correct 36 ms 8268 KB Output is correct
29 Correct 80 ms 12664 KB Output is correct
30 Correct 77 ms 12792 KB Output is correct
31 Correct 81 ms 13232 KB Output is correct
32 Correct 93 ms 17628 KB Output is correct