oj.uz

Submission #173671

# Submission time Handle Problem Language Result Execution time Memory
173671 2020-01-04T23:01:55 Z rzbt One-Way Streets (CEOI17_oneway) C++14
0 / 100
 7 ms 5372 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

vector<pair<int,int> > niz[MAXN];
vector<pair<int,int> > stablo[MAXN];
int n,m,p;
bool most[MAXN],obidjen[MAXN];
int ulaz[MAXN],dub[MAXN];
int predak[MAXN][21];
int grupa[MAXN];
int vreme;
int dokle[MAXN],smer[MAXN];
int leva[MAXN];
char s[MAXN];
int dfsM(int t,int o){
    vreme++;
    ulaz[t]=vreme;
    obidjen[t]=true;
    int minv=vreme;
    for(auto x:niz[t]){

        if(x.F==o)continue;
        int tv;

        if(obidjen[x.F])tv=ulaz[x.F];
        else tv=dfsM(x.F,t);

        if(tv>ulaz[t])most[x.S]=true;
        minv=min(minv,tv);
    }
    return minv;

}

void dfsS(int t,int kad,int h){
    //printf("   %d    %d     grupa\n",t,kad);
    grupa[t]=kad;
    obidjen[t]=true;
    dub[kad]=h;
    for(auto x:niz[t]){
        if(obidjen[x.F])continue;
        if(most[x.S]){
            vreme++;
            stablo[kad].pb(mp(vreme,x.S));
            predak[vreme][0]=kad;
            dfsS(x.F,vreme,h+1);
        }
        else dfsS(x.F,kad,h);

    }
}


int lca(int a,int b){
    if(dub[b]>dub[a])swap(a,b);
    for(int j=20;j>=0;j--)
        if(dub[predak[a][j]]>=dub[b])
            a=predak[a][j];
    if(a==b)return a;
    for(int j=20;j>=0;j--){
        if(predak[a][j]!=predak[b][j]){
            a=predak[a][j];
            b=predak[b][j];
        }
    }
    return predak[a][0];
}

void dfs(int t,int o,int caleg){
    //printf("%d %d\n",t,caleg);
    obidjen[t]=true;
    for(auto x:stablo[t]){
        if(x.F==o)continue;
        dfs(x.F,t,x.S);
    }
    if(o==0 || dokle[t]==0 || dokle[t]==t)return;
    if(smer[t]==1){
        //printf("  1 %d %d %d\n",caleg,t,leva[caleg]);
        if(t==leva[caleg])s[caleg-1]='L';
        else s[caleg-1]='R';
    }else if (smer[t]==-1){
        //printf(" -1 %d %d %d\n",caleg,t,leva[caleg]);
        if(t==leva[caleg])s[caleg-1]='R';
        else s[caleg-1]='L';
    }
    if(dokle[t]==o)return;

    if(dokle[o]==0 || dokle[o]>dokle[t])dokle[o]=dokle[t];
    smer[o]=smer[t];
}


int main()///NE MORA DA VUDE POVEZAN
{
    //freopen("output.txt","w",stdout);
    scanf("%d %d", &n, &m);
    for(int i=1;i<=m;i++){
        int t1,t2;
        scanf("%d %d", &t1, &t2);
        niz[t1].pb(mp(t2,i));
        niz[t2].pb(mp(t1,i));
        //printf("       %d %d\n",i,t1);
        leva[i]=t1;
    }
    for(int i=1;i<=n;i++)
        if(!obidjen[i])dfsM(i,0);
    vreme=0;
    memset(obidjen,0,sizeof(obidjen));
    for(int i=1;i<=n;i++){
        if(!obidjen[i]){
            vreme++;
            dfsS(i,vreme,1);
        }
    }
    for(int j=1;j<21;j++){
        for(int i=1;i<=vreme;i++){
            predak[i][j]=predak[predak[i][j-1]][j-1];
        }
    }
    scanf("%d", &p);
    while(p--){
        int a,b;
        scanf("%d %d", &a, &b);
        a=grupa[a];
        b=grupa[b];
        int najnizi=lca(a,b);

        dokle[a]=dokle[b]=najnizi;
        smer[a]=-1;
        smer[b]=1;
    }
    memset(obidjen,0,sizeof(obidjen));
    for(int i=0;i<m;i++)s[i]='B';
    s[m]=0;
    for(int i=1;i<=m;i++)leva[i]=grupa[leva[i]];
    for(int i=1;i<=n;i++)
        if(!obidjen[i])
            dfs(i,0,0);
    printf("%s",s);
    //printf("   %d\n",most[12]);
    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~
oneway.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p);
     ~~~~~^~~~~~~~~~
oneway.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 7 ms 5368 KB Output is correct
5 Correct 7 ms 5372 KB Output is correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 7 ms 5368 KB Output is correct
8 Correct 7 ms 5368 KB Output is correct
9 Incorrect 7 ms 5240 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 7 ms 5368 KB Output is correct
5 Correct 7 ms 5372 KB Output is correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 7 ms 5368 KB Output is correct
8 Correct 7 ms 5368 KB Output is correct
9 Incorrect 7 ms 5240 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 7 ms 5368 KB Output is correct
5 Correct 7 ms 5372 KB Output is correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 7 ms 5368 KB Output is correct
8 Correct 7 ms 5368 KB Output is correct
9 Incorrect 7 ms 5240 KB Output isn't correct
10 Halted 0 ms 0 KB -