oj.uz

Submission #378438

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

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

typedef int_fast16_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);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

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

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 << 2], 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:87:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   87 |   for(auto x : seg[v]) B.undo();
      |            ^
pipes.cpp:94:11: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   94 |  for(auto x : seg[v]) B.undo();
      |           ^
pipes.cpp: In function 'int main()':
pipes.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14848 KB Output is correct
2 Correct 17 ms 14572 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 14828 KB Output is correct
2 Runtime error 156 ms 19180 KB Memory limit exceeded

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1572 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 1890 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -