oj.uz

Submission #365426

# Submission time Handle Problem Language Result Execution time Memory
365426 2021-02-11T16:24:21 Z LucaDantas 전압 (JOI14_voltage) C++17
45 / 100
 1000 ms 9180 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>,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});
		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, bip] = sv.back();
			auto [a, b] = pp;
			sv.pop_back();
			pai[b] = b;
			color[b] = 0;
			peso[a] -= peso[b];
			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:72:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   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 1 ms 1132 KB Output is correct
5 Correct 3 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 3 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 5728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5344 KB Output is correct
2 Correct 50 ms 5600 KB Output is correct
3 Correct 51 ms 5600 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 267 ms 5344 KB Output is correct
6 Correct 111 ms 5728 KB Output is correct
7 Correct 249 ms 5728 KB Output is correct
8 Correct 284 ms 5728 KB Output is correct
9 Correct 350 ms 5728 KB Output is correct
10 Correct 483 ms 5728 KB Output is correct
11 Correct 222 ms 5728 KB Output is correct
12 Correct 199 ms 5728 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 9180 KB Time limit exceeded
2 Halted 0 ms 0 KB -