Submission #42262

#	Time	Username	Problem	Language	Result	Execution time	Memory
42262		milmillin	Usmjeri (COCI17_usmjeri)	C++14	28 / 140	604 ms	75072 KiB

usmjeri

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> pth[300100];
int p[20][300100];
int dep[300100];

int grp[300100];
int ref[300100];
int col[300100];

vector<int> ppp[300100];

void dfs(int par, int idx,int d) {
	p[0][idx]=par;
	dep[idx]=d;
	for (auto i:pth[idx]) {
		if (i==par) continue;
		dfs(idx,i,d+1);
	}
}

struct lcaInfo {
	int a,b,lca,sz;
};

struct path{
	int a,b;
	lcaInfo l;
};

bool operator< (const path &a, const path &b) {
	if (dep[a.l.lca]!=dep[b.l.lca]) return dep[a.l.lca]<dep[b.l.lca];
	return a.l.sz>a.l.sz;
}



lcaInfo lca(int a,int b) {
	if (dep[a]<dep[b]) swap(a,b);
	//printf("asdd %d %d\n",dep[a],dep[b]);	
	int tmp;
	for (int i=19;i>=0;i--) {
		if (dep[p[i][a]]>dep[b]) {
			//if (dep[p[i][a]]>dep[b]) cur=a;
			a=p[i][a];
		} 
	}
	//printf("asdd %d %d %d %d\n",dep[a],dep[b],a,b);
	tmp=a;
	if (dep[a]!=dep[b]) a=p[0][a];

	if (a==b) return lcaInfo{tmp,0,a,1};
	
	//printf("asd %d %d\n",a,b);

	for (int i=19;i>=0;i--) {
		if (p[i][a]!=p[i][b]) {
			a=p[i][a];
			b=p[i][b];
		}
	}
	return lcaInfo{a,b,p[0][a],2};
}

bool chk[600100];

void ddd(int idx,int c) {
	col[idx]=c;
	for (auto a:ppp[idx]) {
		if (col[a]==c) {
			printf("0\n");
			exit(0);
		} else if (col[a]!=0) {
			continue;
		}
		ddd(a,(c==1)?2:1);
	}
}

int mod = 1000000007;

int poww(int xx) {
	if (xx==0) return 1;
	if (xx==1) return 2;
	long long m = poww(xx/2);
	m=m*m;
	m%=mod;
	if (xx%2) return (2*m)%mod;
	return m;
}

int main () {
	int n,m;
	scanf("%d%d",&n,&m);
	int a,b;
	for (int i=1;i<n;i++) {
		scanf("%d%d",&a,&b);
		pth[a].push_back(b);
		pth[b].push_back(a);
	}
	dfs(1,1,1);
	for (int i=1;i<20;i++) {
		for (int j=1;j<=n;j++) {
			p[i][j]=p[i-1][p[i-1][j]];
		}
	}
	vector<path> qq;	
	for (int i=0;i<m;i++) {
		scanf("%d%d",&a,&b);
		qq.push_back(path{a,b,lca(a,b)});
		//printf("%d %d %d %d %d\n",qq.back().a,qq.back().b,qq.back().l.a,qq.back().l.b,qq.back().l.lca);
	}
	sort(qq.begin(),qq.end());
	
	for (int i=1;i<=n;i++) {
		grp[i]=i;
	}
	int curGrp=n+1;
	int xx,rr,rrr;
	int cura,curb;
	for (auto &i:qq) {
		//printf("%d %d %d\n",i.a,i.b,i.l.lca);
		if (i.l.sz==1) {
			//printf("yy\n");
			if (grp[i.l.a]>n) {
				xx=grp[i.l.a];
				rr=ref[i.l.a];
			} else {
				xx=curGrp++;
				rr=i.l.a;
			}
			//printf("--%d %d\n",xx,rr);
			cura=(i.a==i.l.lca)?i.b:i.a;
			while (cura!=i.l.lca&&grp[cura]<=n) {
				grp[cura]=xx;
				ref[cura]=rr;
				cura=p[0][cura];
			}
		} else {
			xx=-1;
			//printf("--- %d %d\n",i.l.a,i.l.b);
			if (grp[i.l.a]>n) {
				xx=grp[i.l.a];
				rr=ref[i.l.a];
			} else {
				rr=i.l.a;
			}
			if (grp[i.l.b]>n) {
				xx=grp[i.l.b];
				rrr=ref[i.l.b];
			} else {
				rrr=ref[i.l.b];
			}
			if (xx==-1) xx=curGrp++;
			//printf("+++ %d\n",xx);
			cura=i.a;
			curb=i.b;
			while (cura!=i.l.lca&&grp[cura]<=n) {
				grp[cura]=xx;
				ref[cura]=rr;
				//printf("-- %d %d\n",cura,xx);
				cura=p[0][cura];
			}
			while (curb!=i.l.lca&&grp[cura]<=n) {
				grp[curb]=xx;
				ref[curb]=rrr;
				//printf("-- %d %d\n",curb,xx);
				curb=p[0][curb];
			}
			if (rr==rrr) {
				printf("0\n");
				return 0;
			}
			ppp[rrr].push_back(rr);
			ppp[rr].push_back(rrr);
		}	
	}

	for (int i=1;i<=n;i++) {
		if (col[i]==0) {
			ddd(i,1);
		}	
	}

	int cnt=0;
	for (int i=2;i<=n;i++) {
		if (!chk[grp[i]]) {
			chk[grp[i]]=true;
			cnt++;
		}
		//printf("- %d %d\n",i,grp[i]);
	}
	printf("%d\n",poww(cnt));
	return 0;
}

Compilation message (stderr)

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:98:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
usmjeri.cpp:101:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
                      ^
usmjeri.cpp:113:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
                      ^

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14