oj.uz

Submission #378437

# Submission time Handle Problem Language Result Execution time Memory
378437 2021-03-16T19:11:13 Z AriaH Pipes (CEOI15_pipes) C++11
20 / 100
 1866 ms 65536 KB 
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
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);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

struct dsu
{
	int tp = 0, par[N], sz[N];
	vector < pii > hist;
	void init()
	{
		fill(sz, sz + N, 1);
		iota(par, par + N, 0);
	}
	int get(int x)
	{
		return (x == par[x]? x : get(par[x]));
	}
	int unify(int v, int 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;
		pii cu = hist.back();
		hist.pop_back();
		if(cu.F == 0) return;
		par[cu.S] = cu.S;
		sz[cu.F] -= sz[cu.S];
	}
} A, B;

int n, m;

vector < pii > seg[N << 2], vec;

void add(int l, int r, pii 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))
		{
			printf("%d %d\n", vec[tl].F, vec[tl].S);
		}
		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();
	scanf("%d%d", &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:91:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   91 |   for(auto x : seg[v]) B.undo();
      |            ^
pipes.cpp:98:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   98 |  for(auto x : seg[v]) B.undo();
      |           ^
pipes.cpp: In function 'int main()':
pipes.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12396 KB Output is correct
2 Correct 15 ms 12268 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 17388 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 304 ms 23056 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 454 ms 32512 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 622 ms 50192 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 939 ms 64096 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1252 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1530 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1866 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -