| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49296 |
2018-05-25T03:27:56 Z |
Benq |
Pipes (CEOI15_pipes) |
C++14 |
|
1083 ms |
8984 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);
}
}
if (x != z.s && par[z.s].v) child[par[z.s].v].pb({z.s,par[z.s].p0,par[z.s].p1});
}
void makeParent(int B, edge pre) { // check
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;
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);
/*cout << "T " << i << " " << act.get(11) << " ";
for (auto z: child[act.get(11)]) cout << z.v << " ";
cout << par[act.get(11)].v << " ";
cout << "\n";*/
}
// FOR(i,1,n+1) if (act.get(i) == i) cout << "ZZ " << i << " " << comp.get(i) << " " << par[i].v << "\n";
cout.tie(0);
// for (auto j: child[7]) cout << "OOPS " << j.v << " " << act.get(j.v) << "\n";
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?)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4224 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4480 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
4480 KB |
Output is correct |
| 2 |
Correct |
94 ms |
4352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
4752 KB |
Output is correct |
| 2 |
Correct |
193 ms |
4728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
262 ms |
5248 KB |
Output is correct |
| 2 |
Correct |
228 ms |
5496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
369 ms |
7428 KB |
Output is correct |
| 2 |
Correct |
315 ms |
7288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
587 ms |
7720 KB |
Output is correct |
| 2 |
Correct |
566 ms |
7832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
765 ms |
8380 KB |
Output is correct |
| 2 |
Correct |
706 ms |
8824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
909 ms |
8312 KB |
Output is correct |
| 2 |
Correct |
879 ms |
8984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1083 ms |
8148 KB |
Output is correct |
| 2 |
Correct |
1037 ms |
8752 KB |
Output is correct |
