답안 #55549 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55549	2018-07-07T21:50:20 Z	hamzqq9	Usmjeri (COCI17_usmjeri)	C++14	84 / 140	610 ms	58112 KB

usmjeri

#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 1000000007
#define inf 1000000001
#define N 300005
#define LOG 20
#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],anc[N],way[N],FT[N];
int x,y,n,m,C;
vector<int> v[N];

int bul(int node) {

	if(anc[node]==node) return node;

	return anc[node]=bul(anc[node]);

}

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);}

int make_up(int x,int to,int wyx) {

	if(der[x]<=der[to]) return -1;

	if(way[x] && way[x]!=wyx) fail();

	way[x]=wyx;

	int par=make_up(FT[x],to,wyx);

	if(par==-1) par=bul(x);
	else FT[x]=FT[FT[x]];

	if(par!=bul(x)) {
		
		C--;

		anc[bul(x)]=par;

	}

	return par;

}

int go_up(int x,int to) {

	while(x!=to) {

		if(way[x]) return way[x];

		x=baba[0][x];

	}

	return 0;

}

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=2;i<=n;i++) anc[i]=i;

	C=n-1;

	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();

	for(int i=1;i<=n;i++) FT[i]=baba[0][i];

	while(m--) {

		scanf("%d %d",&x,&y);

		int _lca=lca(x,y);

		int way1=go_up(x,_lca);

		if(!way1) {

			way1=3-go_up(y,_lca);

			if(way1==3) {

				way1=1;

			}

		}

		int dad1=make_up(x,_lca,way1);
		int dad2=make_up(y,_lca,3-way1);
	
		if(bul(dad1)!=bul(dad2) && ~dad1 && ~dad2) {

			C--;

			anc[bul(dad1)]=bul(dad2);

		}

	}

	int ans=1;

	for(int i=1;i<=C;i++) ans=ans*2%MOD;

	printf("%d\n",ans);

}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:167: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:175: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:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	58112 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	58112 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	12 ms	58112 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	11 ms	58112 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	460 ms	58112 KB	Output is correct
2	Correct	504 ms	58112 KB	Output is correct
3	Correct	169 ms	58112 KB	Output is correct

Subtask #8
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	610 ms	58112 KB	Output is correct
2	Correct	551 ms	58112 KB	Output is correct
3	Correct	283 ms	58112 KB	Output is correct

Subtask #9
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	554 ms	58112 KB	Output is correct
2	Correct	369 ms	58112 KB	Output is correct
3	Correct	171 ms	58112 KB	Output is correct

Subtask #10
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	509 ms	58112 KB	Output is correct
2	Correct	394 ms	58112 KB	Output is correct
3	Correct	194 ms	58112 KB	Output is correct