oj.uz

Submission #49291

# Submission time Handle Problem Language Result Execution time Memory
49291 2018-05-25T03:11:39 Z Benq Pipes (CEOI15_pipes) C++14
70 / 100
 5000 ms 8920 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) {
		for (auto a: child[x]) if (a.v == act.get(a.v) && a.v != z.s) {
			par[a.v] = edge{z.s,a.p0,a.p1};
			child[z.s].pb(a);
		}
	}

}

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

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,edge{0,0,0});
	// 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 = 50, m = 50;
    // cout << n << " " << m;
    // exit(0);
    F0R(i,m) {
        int a,b; cin >> a >> b;
    	// int a = rand() % n+1,b = rand() % n+1; 
    	ad(a,b);
    }
    // FOR(i,1,n+1) if (act.get(i) == i) cout << "ZZ " << i << " " << comp.get(i) << " " << par[i].v << "\n";
    cout.tie(0);
    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";
}

// 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 Correct 5 ms 4224 KB Output is correct
2 Incorrect 5 ms 4224 KB Wrong number of edges

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4480 KB Output is correct
2 Incorrect 8 ms 4480 KB Wrong number of edges

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 4528 KB Output is correct
2 Correct 93 ms 4472 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 4736 KB Output is correct
2 Correct 186 ms 4728 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 5248 KB Output is correct
2 Correct 233 ms 5496 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 7536 KB Output is correct
2 Correct 318 ms 7288 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 7732 KB Output is correct
2 Correct 549 ms 7732 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 8280 KB Output is correct
2 Execution timed out 5087 ms 6904 KB Time limit exceeded

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 975 ms 8264 KB Output is correct
2 Correct 901 ms 8920 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1118 ms 8128 KB Output is correct
2 Correct 1073 ms 8644 KB Output is correct