oj.uz

답안 #167902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167902 2019-12-10T18:23:23 Z rzbt Usmjeri (COCI17_usmjeri) C++14
84 / 140
 770 ms 89028 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 300005
typedef long long ll;
using namespace std;

int n,m;
vector<pair<int,int> > graf[MAXN];
vector<int> 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] && tb == boja[x]){
            printf("0");
            exit(0);
        }
        if(!obidjen[x])
            moguce(x,!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(gcale[t]);
            dobar[gcale[t]].pb(x.S);
        }
        z+=lol;
    }
    return z;
}
void dfs(int t){
    obidjen[t]=true;
    for(auto x:dobar[t])
        if(!obidjen[x])
            dfs(x);

}


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(g2);
            los[g2].pb(g1);
            dobar[g1].pb(g2);
            dobar[g2].pb(g1);
        }
        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;
    for(int i=1;i<n;i++){

        if(!obidjen[i]){
            dfs(i);
            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

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:93: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:96: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:107: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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 44928 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 416 ms 89028 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 21880 KB Output is correct
2 Incorrect 23 ms 22136 KB Output isn't correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 21880 KB Output is correct
2 Correct 22 ms 21752 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 22520 KB Output is correct
2 Correct 24 ms 22264 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 22520 KB Output is correct
2 Correct 24 ms 22264 KB Output is correct

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 585 ms 65144 KB Output is correct
2 Correct 619 ms 74560 KB Output is correct
3 Incorrect 360 ms 56056 KB Output isn't correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 745 ms 70820 KB Output is correct
2 Correct 723 ms 76920 KB Output is correct
3 Incorrect 481 ms 58956 KB Output isn't correct

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 718 ms 69816 KB Output is correct
2 Correct 588 ms 73964 KB Output is correct
3 Incorrect 475 ms 59128 KB Output isn't correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 754 ms 69792 KB Output is correct
2 Correct 770 ms 77252 KB Output is correct
3 Correct 272 ms 52216 KB Output is correct