提出 #37343598

ソースコード 拡げる

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const int maxn=(2e5)+10;
int n,m,cnt[2];
int col[maxn]; vector<int> g[maxn];
ll C2(ll x) { return x*(x-1)/2; }
ll ans;
void dfs(int u) {
	cnt[col[u]-1]++;
	for (int &v : g[u]) {
		if (col[v]&&col[v]==col[u]) { puts("0"); exit(0); }
		if (col[v]) continue;
		col[v]=3-col[u];
		dfs(v);
	}
}
int main() {
	read(n),read(m);
	int x,y; for (int i=1;i<=m;i++) {
		read(x),read(y);
		g[x].push_back(y),g[y].push_back(x);
	}
	for (int i=1;i<=n;i++) if (!col[i]) {
		cnt[0]=cnt[1]=0;
		col[i]=1,dfs(i);
		ans-=C2(cnt[0]),ans-=C2(cnt[1]);
	}
	ans-=m;
	ans+=C2(n);
	printf("%lld\n",ans);
	
	return 0;
}

提出情報

提出日時
問題 D - Make Bipartite 2
ユーザ wygz
言語 C++ (GCC 9.2.1)
得点 400
コード長 1141 Byte
結果 AC
実行時間 137 ms
メモリ 24700 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 3
AC × 47
セット名 テストケース
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, example0.txt, example1.txt, example2.txt
ケース名 結果 実行時間 メモリ
000.txt AC 11 ms 8320 KiB
001.txt AC 7 ms 8224 KiB
002.txt AC 10 ms 9004 KiB
003.txt AC 13 ms 8420 KiB
004.txt AC 63 ms 15728 KiB
005.txt AC 133 ms 21612 KiB
006.txt AC 137 ms 24700 KiB
007.txt AC 125 ms 24652 KiB
008.txt AC 19 ms 10996 KiB
009.txt AC 20 ms 10420 KiB
010.txt AC 19 ms 10312 KiB
011.txt AC 21 ms 9808 KiB
012.txt AC 39 ms 11328 KiB
013.txt AC 35 ms 10780 KiB
014.txt AC 69 ms 14256 KiB
015.txt AC 18 ms 9900 KiB
016.txt AC 10 ms 9200 KiB
017.txt AC 13 ms 8996 KiB
018.txt AC 15 ms 9152 KiB
019.txt AC 73 ms 13460 KiB
020.txt AC 13 ms 8996 KiB
021.txt AC 25 ms 10816 KiB
022.txt AC 20 ms 9080 KiB
023.txt AC 14 ms 9188 KiB
024.txt AC 45 ms 11680 KiB
025.txt AC 17 ms 9956 KiB
026.txt AC 10 ms 9140 KiB
027.txt AC 10 ms 9020 KiB
028.txt AC 12 ms 9116 KiB
029.txt AC 45 ms 12348 KiB
030.txt AC 37 ms 11760 KiB
031.txt AC 31 ms 11344 KiB
032.txt AC 22 ms 10524 KiB
033.txt AC 12 ms 8444 KiB
034.txt AC 71 ms 13760 KiB
035.txt AC 14 ms 9196 KiB
036.txt AC 22 ms 9824 KiB
037.txt AC 12 ms 9256 KiB
038.txt AC 11 ms 9004 KiB
039.txt AC 99 ms 16904 KiB
040.txt AC 48 ms 13736 KiB
041.txt AC 22 ms 10888 KiB
042.txt AC 21 ms 10384 KiB
043.txt AC 11 ms 8304 KiB
example0.txt AC 10 ms 8224 KiB
example1.txt AC 10 ms 8292 KiB
example2.txt AC 10 ms 8252 KiB