oj.uz

Submission #49288

# Submission time Handle Problem Language Result Execution time Memory
49288 2018-05-25T02:31:53 Z Benq Pipes (CEOI15_pipes) C++14
0 / 100
 5000 ms 6776 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

struct edge {
	int v;
	int p0, p1;
};

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> comp, act;
int n,m;
edge par[MX];
vector<edge> child[MX];
bool ok[MX];

int lca(int A, int B) { // check
	if (A == B) return A;
	int a = A, b = B;
	ok[a] = ok[b] = 1;

	int ans;

	while (1) {
		if (par[a].v != 0) {
			a = par[a].v;
			if (ok[a]) {
				ans = a;
				break;
			}
			ok[a] = 1;
		}
		if (par[b].v != 0) {
			b = par[b].v;
			if (ok[b]) {
				ans = b;
				break;
			}
			ok[b] = 1;
		}
	}

	for (; A != a; A = par[A].v) ok[A] = 0;
	ok[A] = 0;

	for (; B != b; B = par[B].v) ok[B] = 0;
	ok[B] = 0;

	return ans;
}

void uniteSame(int A, int B, int a, int b)  {// check
	int x = lca(A,B);
	vi v = {x};
	while (A != x) {
		v.pb(A);
		A = par[A].v;
	}
	while (B != x) {
		v.pb(B);
		B = par[B].v;
	}
	pi z = {-1,-1};
	for (int x: v) z = max(z,{sz(child[x]),x});
	par[z.s] = par[x];
	for (int x: v) if (x != z.s) act.unite(z.s,x);
	for (int x: v) if (x != z.s && x == act.get(x)) {
		for (auto a: child[x]) if (a.v == act.get(a.v)) {
			par[a.v] = edge{z.s,a.p0,a.p1};
			child[z.s].pb(a);
		}
	}

}

void makeParent(int B, int pre = 0) { // check
	vector<edge> adj;
	if (par[B].v && par[B].v != pre) adj.pb(par[B]);
	for (auto a: child[B]) 
		if (a.v == act.get(a.v) && a.v != pre) 
			adj.pb(a);
	if (pre == 0) par[B] = edge{0,0,0};
	child[B].clear();
	for (auto i: adj) {
		par[i.v] = edge{B,i.p0,i.p1};
		child[B].pb(i);
		makeParent(i.v,B);
	}
}

void uniteDif(int A, int B, int a, int b) {
	if (comp.sz[comp.get(A)] < comp.sz[comp.get(B)]) swap(A,B);
	makeParent(B);
	// cout << "AH " << A << " " << B << " " << act.get(A) << " " << act.get(B) << "\n";
	par[B] = {A,a,b};
	child[A].pb(edge{B,a,b});
	comp.unite(A,B);
}

void ad(int a, int b) {
	int A = act.get(a), B = act.get(b);
	if (A == B) return;
	if (comp.get(A) != comp.get(B)) uniteDif(A,B,a,b);
	else uniteSame(A,B,a,b);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt","r",stdin);
    cin >> n >> m;
    // n = 100000, m = 1000000;
    // cout << n << " " << m;
    // exit(0);
    F0R(i,m) {
    	// int a = rand() % n+1,b = rand() % n+1; 
    	int a,b; cin >> a >> b;
    	// if (a == 4 && b == 10) break;
    	// cout << "HI " << a << " " << b << "\n";
    	ad(a,b);
    }
    FOR(i,1,n+1) if (act.get(i) == i) 
		for (auto j: child[i]) if (act.get(j.v) == j.v) cout << j.p0 << " " << j.p1 << "\n";
    // cout << par[2].v << "\n";
    // FOR(i,1,n+1) cout << i << " " << act.get(i) << " " << par[i].v << " | " << "\n";
    // makeParent(10);
    // FOR(i,1,n+1) cout << i << " " << act.get(i) << " " << par[i].v << " | " << "\n";
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 4224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5064 ms 4352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 4352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5094 ms 4480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5060 ms 4836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5099 ms 6008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5081 ms 6144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5058 ms 6776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5047 ms 6776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5083 ms 6524 KB Time limit exceeded
2 Halted 0 ms 0 KB -