oj.uz

Submission #378440

# Submission time Handle Problem Language Result Execution time Memory
378440 2021-03-16T19:31:39 Z AriaH Pipes (CEOI15_pipes) C++11
30 / 100
 1705 ms 29284 KB 
/** I can do this all day **/

#include <bits/stdc++.h>
using namespace std;

typedef uint_fast32_t                   ll;
typedef long double                 ld;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    (int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 1e5 + 3;

struct dsu
{
	ll tp = 0, par[N], sz[N];
	vector < pll > hist;
	void init()
	{
		fill(sz, sz + N, 1);
		iota(par, par + N, 0);
	}
	ll get(ll x)
	{
		return (x == par[x]? x : get(par[x]));
	}
	ll unify(ll v, ll u)
	{
		v = get(v), u = get(u);
		if(v == u)
		{
			if(tp) hist.push_back(Mp(0, 0));
			return 0;
		}
		if(sz[u] > sz[v]) swap(v, u);
		par[u] = v;
		sz[v] += sz[u];
		if(tp) hist.push_back(Mp(v, u));
		return 1;
	}
	void undo()
	{
		if(hist.empty()) return;
		pll cu = hist.back();
		hist.pop_back();
		if(cu.F == 0) return;
		par[cu.S] = cu.S;
		sz[cu.F] -= sz[cu.S];
	}
} A, B;

ll n, m;

vector < pll > seg[N], vec;

void add(int l, int r, pll e, int v = 1, int tl = 0, int tr = SZ(vec) - 1)
{
	if(l > tr || r < tl || l > r) return;
	if(l <= tl && tr <= r)
	{
		seg[v].push_back(e);
		return;
	}
	int mid = (tl + tr) >> 1;
	add(l, r, e, v << 1, tl, mid);
	add(l, r, e, v << 1 | 1, mid + 1, tr);
}

void solve(int v = 1, int tl = 0, int tr = SZ(vec) - 1)
{
	for(auto x : seg[v]) B.unify(x.F, x.S);
	if(tl == tr)
	{
		if(B.get(vec[tl].F) != B.get(vec[tl].S))
		{
			cout << vec[tl].F << " " << vec[tl].S << "\n";
		}
		for(auto x : seg[v]) B.undo();
		seg[v].clear(); seg[v].shrink_to_fit();
		return;
	}
	int mid = (tl + tr) >> 1;
	solve(v << 1, tl, mid);
	solve(v << 1 | 1, mid + 1, tr);
	for(auto x : seg[v]) B.undo();
	seg[v].clear(); seg[v].shrink_to_fit();
}

int main()
{
	A.init(), B.init();
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		if(A.unify(a, b))
		{
			vec.push_back(Mp(a, b));
		}
		else
		{
			B.unify(a, b);
		}
	}
	for(int i = 0; i < SZ(vec); i ++)
	{
		add(0, i - 1, vec[i]);
		add(i + 1, SZ(vec) - 1, vec[i]);
	}
	B.tp = 1;
	solve();
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message

pipes.cpp: In function 'void solve(int, int, int)':
pipes.cpp:82:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   82 |   for(auto x : seg[v]) B.undo();
      |            ^
pipes.cpp:89:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   89 |  for(auto x : seg[v]) B.undo();
      |           ^
pipes.cpp: In function 'int main()':
pipes.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int i = 1; i <= m; i ++)
      |                 ~~^~~~
pipes.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5996 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7552 KB Output is correct
2 Correct 12 ms 7532 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 7252 KB Output is correct
2 Correct 154 ms 7020 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 9960 KB Output is correct
2 Runtime error 309 ms 20968 KB Memory limit exceeded

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 14964 KB Output is correct
2 Runtime error 389 ms 29284 KB Memory limit exceeded

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 527 ms 14148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 841 ms 14556 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1091 ms 15196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1369 ms 15252 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1705 ms 21420 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -