| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 167902 |
2019-12-10T18:23:23 Z |
rzbt |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
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);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
213 ms |
44928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
416 ms |
89028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
21880 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
22136 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
21880 KB |
Output is correct |
| 2 |
Correct |
22 ms |
21752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
22520 KB |
Output is correct |
| 2 |
Correct |
24 ms |
22264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
22520 KB |
Output is correct |
| 2 |
Correct |
24 ms |
22264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
