제출 #365429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365429		LucaDantas	전압 (JOI14_voltage)	C++17	100 / 100	250 ms	9708 KiB

voltage

#include<cstdio>
#include<vector>
#include<utility>
using namespace std;

constexpr int maxn = 1e5+10;

struct DSU
{
	int pai[maxn], peso[maxn], color[maxn], bp = 1;
	DSU() {for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1;}
	vector<pair<pair<int,int>,pair<int,int>>> sv;
	int find(int x, int& c) {
		while(pai[x] != x) {
			c ^= color[x];
			x = pai[x];
		}
		return pai[x];
	}
	void join(int a, int b) {
		int ca = 0, cb = 0;
		a = find(a, ca), b = find(b, cb);
		if(peso[a] < peso[b])
			swap(a, b), swap(ca, cb);
		sv.push_back({{a, b}, {bp, peso[a]}});
		if(a == b) return (void)(bp = (bp && ca!=cb));
		pai[b] = a;
		peso[a] += peso[b];
		color[b] = 1^ca^cb;
	}
	void rollback(int t) {
		while((int)sv.size() > t) {
			auto [pp, pp2] = sv.back();
			auto [a, b] = pp;
			auto [bip, p_a] = pp2;
			sv.pop_back();
			pai[b] = b;
			color[b] = 0;
			peso[a] = p_a;
			bp = bip;
		}
	}	
} dsu;

vector<pair<int,int>> edges;

int ans = 0;

void solve(int l, int r) {
	if(l == r) {
		auto [a, b] = edges[l];
		int ca = 0, cb = 0;
		if(dsu.find(a, ca) != dsu.find(b, cb) || ca == cb) ++ans;
		return;
	}
	int m = (l+r) >> 1;
	int t = (int)dsu.sv.size();
	for(int i = l; i <= m; i++) {
		dsu.join(edges[i].first, edges[i].second);
		if(!dsu.bp) break;
	}
	if(dsu.bp) solve(m+1, r);
	dsu.rollback(t);
	for(int i = m+1; i <= r; i++) {
		dsu.join(edges[i].first, edges[i].second);
		if(!dsu.bp) break;
	}
	if(dsu.bp) solve(l, m);
	dsu.rollback(t);
}

int main() {
	int n, m; scanf("%d %d", &n, &m);
	for(int i = 0, a, b; i < m; i++)
		scanf("%d %d", &a, &b), edges.push_back({a, b});
	solve(0, m-1);
	printf("%d\n", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

voltage.cpp: In function 'int main()':
voltage.cpp:73:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |   scanf("%d %d", &a, &b), edges.push_back({a, b});
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45