제출 #378438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378438		AriaH	Pipes (CEOI15_pipes)	C++11	20 / 100	1890 ms	65536 KiB

pipes

/** 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 **/

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10