제출 #55525

#제출 시각아이디문제언어결과실행 시간메모리
55525hamzqq9Usmjeri (COCI17_usmjeri)C++14
0 / 140
785 ms103820 KiB
#include<bits/stdc++.h> #define lf double #define ll long long #define ull unsigned ll #define ii pair<int,int> #define li pair<ll,int> #define iii pair<ii,int> #define iiii pair<ii,ii> #define iiii2 pair<int,iii> #define lii pair<ll,ii> #define lolo pair<ll,ll> #define heap priority_queue #define mp make_pair #define st first #define nd second #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define all(x) x.begin(),x.end() #define len(x) strlen(x) #define sz(x) (int) x.size() #define orta ((bas+son)/2) #define min3(x,y,z) min(min(x,y),z) #define max3(x,y,z) max(max(x,y),z) #define umin(x,y) x=min(x,y) #define umax(x,y) x=max(x,y) #define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" " #define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar() #define MOD 1234567891 #define inf 1000000001 #define N 300005 #define LOG 34 #define magic 100 #define MAX 1000005 #define KOK 350 #define EPS 0.000000000001 #define pw(x) 1ll*((1ll)<<(x)) #define PI 3.1415926535 using namespace std; int baba[LOG+2][N],der[N],tot[N],way[N]; int x,y,n,m,C; vector<int> v[N]; int lca(int x,int y) { if(der[x]<der[y]) swap(x,y); int dx=der[x]; for(int i=LOG-1;i>=0;i--) { if(dx-pw(i)>=der[y]) { dx-=pw(i); x=baba[i][x]; } } if(x==y) return x; for(int i=LOG-1;i>=0;i--) { if(baba[i][x]!=baba[i][y]) { x=baba[i][x]; y=baba[i][y]; } } return baba[0][x]; } void build_lca() { for(int i=1;i<LOG;i++) { for(int j=1;j<=n;j++) { baba[i][j]=baba[i-1][baba[i-1][j]]; } } } void fail() {printf("0");exit(0);} void make_up(int x,int to,int wyx) { while(x!=to && !way[x]) { way[x]=wyx; x=baba[0][x]; } if(x!=to && way[x]!=wyx) fail(); } int go_up(int x,int to) { while(x!=to) { if(way[x]) return way[x]; x=baba[0][x]; } return 0; } void dfs(int node,int ata) { int ok=0; for(int i:v[node]) { if(i==ata) continue ; dfs(i,node); tot[node]+=tot[i]; ok|=(tot[i]>0); } if(!tot[node]) C+=(ata>0)+ok; } void dfs1(int node,int ata) { baba[0][node]=ata; der[node]=der[ata]+1; for(int i:v[node]) { if(i==ata) continue ; dfs1(i,node); } } int main() { #if 0 freopen("input.txt","r",stdin); #endif scanf("%d %d",&n,&m); for(int i=1;i<n;i++) { scanf("%d %d",&x,&y); v[x].pb(y); v[y].pb(x); } dfs1(1,0); build_lca(); while(m--) { scanf("%d %d",&x,&y); tot[x]++; tot[y]++; int _lca=lca(x,y); tot[_lca]-=2; int way1=go_up(x,_lca); if(!way1) { way1=3-go_up(y,_lca); if(way1==3) { way1=1; } } make_up(x,_lca,way1); make_up(y,_lca,3-way1); } dfs(1,0); int ans=1; for(int i=1;i<=C;i++) ans=ans*2%MOD; printf("%d\n",ans); }

컴파일 시 표준 에러 (stderr) 메시지

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
usmjeri.cpp:172:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
usmjeri.cpp:184:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...