Submission #7637264


Source Code Expand

Copy
#include<bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 100005;

struct disj{
	int pa[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

int n; lint m; int q;
vector<pi>v;
int main(){
	scanf("%d %lld %d",&n,&m, &q);
	disj.init(n);
	int compCnt = n;
	while(q--){
		int a, b, c;
		scanf("%d %d %d",&a,&b,&c);
		if(c == 0){
			compCnt -= disj.uni(a, b);
		}
		else{
			v.emplace_back(a, b);
		}
	}
	for(auto &i : v){
		if(disj.find(i.first) == disj.find(i.second)){
			puts("No");
			return 0;
		}
	}
	if(m == n - 1){
		if(sz(v)) puts("No");
		else puts("Yes");
		return 0;
	}
	if(compCnt == 1){
		puts("No");
		return 0;
	}
	if(compCnt == 2){
		puts("No");
		return 0;
	}
	lint st = n - 1;
	lint ed = n - 1 + 1ll * (compCnt) * (compCnt - 1) / 2;
	if(st <= m && m <= ed){
		puts("Yes");
	}
	else puts("No");
}

Submission Info

Submission Time
Task D - Unique Path
User koosaga
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1148 Byte
Status WA
Exec Time 27 ms
Memory 1784 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:27:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld %d",&n,&m, &q);
                               ^
./Main.cpp:32:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&c);
                             ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 37
WA × 2
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 26 ms 512 KB
01-04.txt AC 26 ms 512 KB
01-05.txt AC 26 ms 512 KB
01-06.txt AC 24 ms 1528 KB
01-07.txt AC 24 ms 1656 KB
01-08.txt AC 24 ms 1656 KB
01-09.txt AC 24 ms 1656 KB
01-10.txt AC 26 ms 896 KB
01-11.txt AC 26 ms 896 KB
01-12.txt AC 25 ms 1148 KB
01-13.txt AC 26 ms 896 KB
01-14.txt WA 26 ms 768 KB
01-15.txt AC 26 ms 768 KB
01-16.txt AC 26 ms 512 KB
01-17.txt AC 25 ms 1020 KB
01-18.txt AC 26 ms 512 KB
01-19.txt AC 26 ms 512 KB
01-20.txt AC 26 ms 640 KB
01-21.txt AC 26 ms 640 KB
01-22.txt AC 26 ms 640 KB
01-23.txt AC 24 ms 1784 KB
01-24.txt AC 24 ms 1784 KB
01-25.txt AC 24 ms 1784 KB
01-26.txt AC 24 ms 1784 KB
01-27.txt AC 26 ms 1276 KB
01-28.txt AC 26 ms 1276 KB
01-29.txt AC 25 ms 1276 KB
01-30.txt AC 26 ms 1276 KB
01-31.txt WA 26 ms 1276 KB
01-32.txt AC 25 ms 1276 KB
01-33.txt AC 27 ms 640 KB
01-34.txt AC 25 ms 1276 KB
01-35.txt AC 26 ms 640 KB
01-36.txt AC 26 ms 640 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB