| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 167931 |
2019-12-10T20:26:50 Z |
rzbt |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
751 ms |
96908 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],boja2[MAXN];
bool boja[MAXN],obidjen[MAXN];
const int MOD = 1e9+7;
bool nasp,nasd;
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){
if(boja2[t]==1)nasp=true;
else if(boja2[t]==2)nasd=true;
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);
}
}
for(int i=1;i<n;i++){
if(obidjen[i]){
boja2[i]=boja[i]+1;
//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]){
nasp=false;
nasd=false;
dfs(i);
if(nasp && nasd){
printf("0");
exit(0);
}
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:97: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:100: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:111: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 |
215 ms |
48644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
427 ms |
96908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
21880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
22012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
22648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
22776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
594 ms |
74000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
751 ms |
78480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
725 ms |
78388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
705 ms |
78624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
