Submission #167906

#	Time	Username	Problem	Language	Result	Execution time	Memory
167906		rzbt	Usmjeri (COCI17_usmjeri)	C++14	28 / 140	778 ms	94712 KiB

usmjeri

#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 300005
typedef long long ll;
using namespace std;

int n,m;
vector<pair<int,int> > graf[MAXN], los[MAXN],dobar[MAXN];
int cale[MAXN][22];
int gcale[MAXN];
int dub[MAXN];
int sab[MAXN];
bool boja[MAXN],obidjen[MAXN];
const int MOD = 1e9+7;

void init(int t,int o,int g,int h){

    if(o){
        cale[t][0]=o;
        gcale[t]=g;
    }
    dub[t]=h;
    for(auto x:graf[t])
        if(x.F!=o)
            init(x.F,t,x.S,h+1);
}


int lca(int a,int b){
    if(dub[a]<dub[b])swap(a,b);
    for(int j=21;j>=0;j--)
        if(dub[cale[a][j]]>=dub[b])a=cale[a][j];
    if(a==b)return a;

    for(int j=21;j>=0;j--){
        if(cale[a][j]!=cale[b][j]){
            a=cale[a][j];
            b=cale[b][j];
        }
    }
    return cale[a][0];
}
int predak(int a,int h){

    for(int j=21;j>=0;j--)
        if(dub[cale[a][j]]>=h)a=cale[a][j];
    return a;
}

void moguce(int t,bool tb){
    //printf(" %d %d\n",t,tb);
    obidjen[t]=true;
    boja[t]=tb;
    for(auto x:los[t]){
        if(obidjen[x.F] && tb == boja[x.F]){
            printf("0");
            exit(0);
        }
        if(!obidjen[x.F])
            moguce(x.F,!tb);
    }
}

int konstruisi(int t,int o){
    int z=sab[t];
    for(auto x:graf[t]){
        if(x.F==o)continue;
        int lol=konstruisi(x.F,t);
        if(lol && o){
            dobar[x.S].pb(mp(gcale[t],0));
            dobar[gcale[t]].pb(mp(x.S,0));
        }
        z+=lol;
    }
    return z;
}
void dfs(int t,bool bo){
    obidjen[t]=true;
    for(auto x:dobar[t]){
        if(obidjen[t] && x.S && bo == boja[x.F]){
            printf("0");
            exit(0);
        }
        if(obidjen[t] && !x.S && bo != boja[x.F]){
            printf("0");
            exit(0);
        }
        if(!obidjen[x.F])
            dfs(x.F,(x.S?!bo:bo));
    }
    for(auto x:los[t]){
        if(obidjen[t] && x.S && bo == boja[x.F]){
            printf("0");
            exit(0);
        }
        if(obidjen[t] && !x.S && bo != boja[x.F]){
            printf("0");
            exit(0);
        }
        if(!obidjen[x.F])
            dfs(x.F,(x.S?!bo:bo));
    }

}


int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1;i<n;i++){
        int t1,t2;
        scanf("%d %d", &t1, &t2);
        graf[t1].pb(mp(t2,i));
        graf[t2].pb(mp(t1,i));
    }
    init(1,0,0,0);
    for(int j=1;j<22;j++)
        for(int i=1;i<=n;i++)
            cale[i][j]=cale[cale[i][j-1]][j-1];
    dub[0]=-1;
    for(int i=1;i<=m;i++){
        int t1,t2;
        scanf("%d %d", &t1, &t2);
        //printf("    %d\n",lca(t1,t2));
        if(dub[t1]<dub[t2])swap(t1,t2);
        int l=lca(t1,t2);
        if(t2!=l){
            int g1=gcale[predak(t1,dub[l]+1)];
            int g2=gcale[predak(t2,dub[l]+1)];
            los[g1].pb(mp(g2,1));
            los[g2].pb(mp(g1,1));
        }
        sab[t1]++;
        sab[predak(t1,dub[l]+1)]--;
        if(t2!=l){
            sab[t2]++;
            sab[predak(t2,dub[l]+1)]--;
        }
    }
    for(int i=1;i<n;i++){

        if(!obidjen[i]){
            moguce(i,false);
            //printf("lol %d\n",i);
        }
    }
    memset(obidjen,0,sizeof(obidjen));
    konstruisi(1,0);
    int bk=0;
    memset(boja,0,sizeof(boja));
    for(int i=1;i<n;i++){

        if(!obidjen[i]){
            dfs(i,false);
            bk++;
            //printf("lol %d\n",i);
        }
    }
    int res=1;
    for(int i=1;i<=bk;i++){
        res=(res+res)%(MOD);
        //if(res==406647669)printf("    %d     %d\n",i,bk);
    }
    printf("%d",res);
    return 0;
}

Compilation message (stderr)

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
usmjeri.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~
usmjeri.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14