oj.uz

Submission #369990

# Submission time Handle Problem Language Result Execution time Memory
369990 2021-02-22T21:14:52 Z luciocf 전압 (JOI14_voltage) C++14
100 / 100
 440 ms 10764 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e5+10;

int n, m, C, B;
pii edge[maxn];
bool ans[maxn];

struct DSU
{
	int pai[maxn], peso[maxn], edge[maxn];
	int cc;
	bool bp;

	struct RollBack
	{
		int u, v, pu, c;
		bool b;
	};

	stack<RollBack> stk;

	void init(void)
	{
		bp = 1, cc = n;
		for (int i = 0; i < maxn; i++)
			pai[i] = i, peso[i] = 1;
	}

	int Find(int x, int &c)
	{
		if (pai[x] == x) return x;

		c ^= edge[x];

		return Find(pai[x], c);
	}

	bool Join(int x, int y)
	{
		int cx = 0, cy = 0;
		x = Find(x, cx), y = Find(y, cy);

		if (peso[x] < peso[y])
		{
			swap(x, y);
			swap(cx, cy);
		}

		stk.push({x, y, peso[x], cc, bp});

		if (x == y) return bp = (bp && (cx != cy));

		cc--;
		pai[y] = x, peso[x] += peso[y];
		edge[y] = cx ^ cy ^ 1;

		return 1;
	}

	void rollback(int x)
	{
		while (stk.size() > x)
		{
			auto E = stk.top(); stk.pop();

			peso[E.u] = E.u;
			pai[E.v] = E.v, edge[E.v] = 0;
			cc = E.c, bp = E.b;
		}
	}
} dsu;

void solve(int l, int r)
{
	if (l > r) return;

	int mid = (l+r)>>1;
	int s0 = dsu.stk.size();

	for (int i = r; i >= mid; i--)
		dsu.Join(edge[i].ff, edge[i].ss);

	solve(l, mid-1);

	dsu.rollback(s0);

	for (int i = l; i <= mid; i++)
		dsu.Join(edge[i].ff, edge[i].ss);

	solve(mid+1, r);

	dsu.rollback((int)dsu.stk.size()-1);

	for (int i = mid+1; i <= r; i++)
		dsu.Join(edge[i].ff, edge[i].ss);

	ans[mid] = (dsu.bp && (dsu.cc > C || !B));

	dsu.rollback(s0);
}

int main(void)
{
	scanf("%d %d", &n, &m);

	dsu.init();

	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d", &edge[i].ff, &edge[i].ss);
		dsu.Join(edge[i].ff, edge[i].ss);
	}

	C = dsu.cc, B = dsu.bp;
	dsu.rollback(0);

	solve(1, m);

	int tot = 0;
	for (int i = 1; i <= m; i++)
		if (ans[i])
			++tot;

	printf("%d\n", tot);
}

Compilation message

voltage.cpp: In member function 'void DSU::rollback(int)':
voltage.cpp:70:21: warning: comparison of integer expressions of different signedness: 'std::stack<DSU::RollBack>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |   while (stk.size() > x)
      |          ~~~~~~~~~~~^~~
voltage.cpp: In function 'int main()':
voltage.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |   scanf("%d %d", &edge[i].ff, &edge[i].ss);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 6404 KB Output is correct
2 Correct 209 ms 6512 KB Output is correct
3 Correct 92 ms 6512 KB Output is correct
4 Correct 207 ms 6384 KB Output is correct
5 Correct 16 ms 2412 KB Output is correct
6 Correct 211 ms 6584 KB Output is correct
7 Correct 207 ms 6384 KB Output is correct
8 Correct 209 ms 6384 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6000 KB Output is correct
2 Correct 63 ms 6360 KB Output is correct
3 Correct 67 ms 6380 KB Output is correct
4 Correct 2 ms 1900 KB Output is correct
5 Correct 164 ms 5540 KB Output is correct
6 Correct 177 ms 6384 KB Output is correct
7 Correct 234 ms 6508 KB Output is correct
8 Correct 213 ms 6456 KB Output is correct
9 Correct 217 ms 6380 KB Output is correct
10 Correct 215 ms 6508 KB Output is correct
11 Correct 177 ms 6508 KB Output is correct
12 Correct 207 ms 6380 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 9712 KB Output is correct
2 Correct 135 ms 10480 KB Output is correct
3 Correct 2 ms 1900 KB Output is correct
4 Correct 245 ms 6892 KB Output is correct
5 Correct 238 ms 6716 KB Output is correct
6 Correct 224 ms 6872 KB Output is correct
7 Correct 386 ms 10536 KB Output is correct
8 Correct 370 ms 10480 KB Output is correct
9 Correct 363 ms 10628 KB Output is correct
10 Correct 329 ms 10480 KB Output is correct
11 Correct 269 ms 10480 KB Output is correct
12 Correct 336 ms 10480 KB Output is correct
13 Correct 313 ms 10564 KB Output is correct
14 Correct 440 ms 10428 KB Output is correct
15 Correct 346 ms 10556 KB Output is correct
16 Correct 363 ms 10436 KB Output is correct
17 Correct 376 ms 10564 KB Output is correct
18 Correct 339 ms 10764 KB Output is correct