oj.uz

Submission #365429

# Submission time Handle Problem Language Result Execution time Memory
365429 2021-02-11T16:31:27 Z LucaDantas 전압 (JOI14_voltage) C++17
100 / 100
 250 ms 9708 KB 
#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);
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 2 ms 1132 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 3 ms 1132 KB Output is correct
11 Correct 1 ms 1132 KB Output is correct
12 Correct 1 ms 1132 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4832 KB Output is correct
2 Correct 143 ms 5600 KB Output is correct
3 Correct 34 ms 5728 KB Output is correct
4 Correct 39 ms 5728 KB Output is correct
5 Correct 10 ms 1772 KB Output is correct
6 Correct 134 ms 5600 KB Output is correct
7 Correct 140 ms 5600 KB Output is correct
8 Correct 155 ms 5600 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4704 KB Output is correct
2 Correct 50 ms 4704 KB Output is correct
3 Correct 50 ms 4704 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 122 ms 4620 KB Output is correct
6 Correct 112 ms 4832 KB Output is correct
7 Correct 163 ms 4832 KB Output is correct
8 Correct 121 ms 4832 KB Output is correct
9 Correct 142 ms 4832 KB Output is correct
10 Correct 133 ms 4832 KB Output is correct
11 Correct 52 ms 4832 KB Output is correct
12 Correct 94 ms 4832 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7644 KB Output is correct
2 Correct 95 ms 9564 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 135 ms 5728 KB Output is correct
5 Correct 177 ms 5728 KB Output is correct
6 Correct 124 ms 5728 KB Output is correct
7 Correct 240 ms 9692 KB Output is correct
8 Correct 225 ms 9564 KB Output is correct
9 Correct 191 ms 9564 KB Output is correct
10 Correct 203 ms 9692 KB Output is correct
11 Correct 53 ms 8540 KB Output is correct
12 Correct 78 ms 9564 KB Output is correct
13 Correct 95 ms 9564 KB Output is correct
14 Correct 250 ms 9564 KB Output is correct
15 Correct 75 ms 9708 KB Output is correct
16 Correct 222 ms 9564 KB Output is correct
17 Correct 235 ms 9564 KB Output is correct
18 Correct 179 ms 9564 KB Output is correct