| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 65794 |
2018-08-08T20:39:53 Z |
Benq |
Collapse (JOI18_collapse) |
C++11 |
|
0 ms |
0 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;
#define LOCAL
#ifdef LOCAL
#else
#include "collapse.h"
#endif
const int BLOCK = 600;
int N;
struct DSU { // persistent DSU
vpi par[MX], child[MX];
int numComp[MX];
DSU() {
F0R(i,N) {
par[i].pb({-1,i});
child[i].pb({-1,i});
}
}
int getComp(int ti) { return numComp[ti]; }
int get(int ti, int x) { return prev(ub(all(par[x]),mp(ti,MOD)))->s; }
void unite(int ti, int x, int y) {
x = par[x].back().s, y = par[y].back().s;
if (x == y) return;
numComp[ti] --;
if (sz(child[x]) < sz(child[y])) swap(x,y);
for (auto a: child[y]) {
par[a.s].pb({ti,x});
child[x].pb({ti,a.s});
}
}
};
DSU A,B;
vi ans;
vector<array<int,3>> change;
vpi tri[MX];
set<pi> cedge, tedge;
vi st[MX], en[MX];
void genDSU() {
F0R(i,N) st[i].clear(), en[i].clear();
for (auto a: cedge) {
st[a.f].pb(a.s);
en[a.s].pb(a.f);
}
A = DSU(), B = DSU();
F0R(i,N) {
A.numComp[i] = (i?A.numComp[i-1]:0)+1;
for (auto a: en[i]) A.unite(i,a,i);
}
// cout << "OH " << A.numComp[4] << " " << A.get(0,4) << "\n";
F0R(i,N) {
B.numComp[i] = (i?B.numComp[i-1]:0)+1;
for (auto a: st[N-1-i]) B.unite(i,a,N-1-i);
}
}
int m[MX];
struct realDSU {
int par[2*BLOCK];
void init(int co) {
F0R(i,co) par[i] = i;
}
int get(int x) { // path compression
if (par[x] != x) par[x] = get(par[x]);
return par[x];
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return 0;
if (rand()&1) swap(x,y);
par[y] = x;
return 1;
}
};
realDSU R;
int mini(const vpi& v) {
int co = 0;
for (auto a: v) m[a.f] = m[a.s] = -1;
for (auto& a: v) {
if (m[a.f] == -1) m[a.f] = co ++;
if (m[a.s] == -1) m[a.s] = co ++;
}
R.init(co);
int res = 0;
for (auto a: v) if (R.unite(m[a.f],m[a.s])) res ++;
// cout << "AH " << co << " " << res << "\n";
return res;
}
int solve(int x) {
int t0 = x, t1 = N-1-(x+1);
int ret = A.getComp(t0)+B.getComp(t1);
vpi ed[2];
for (auto a: tedge) {
// cout << "HA " << t0 << " " << t1 << " " << a.f << " " << a.s << "\n";
if (a.s <= x) {
ed[0].pb({A.get(t0,a.f),A.get(t0,a.s)});
} else if (a.f >= x+1) {
ed[1].pb({B.get(t1,a.f),B.get(t1,a.s)});
}
}
// return 0;
int ans = ret-mini(ed[0])-mini(ed[1]);
/*cout << "HUH " << x << " " << ret << " " << sz(ed[0]) << " " << sz(ed[1]) << " " << ans << "\n";
if (sz(ed[0])) cout << ed[0][0].f << " " << ed[0][0].s << "\n";
if (sz(ed[1])) cout << ed[1][0].f << " " << ed[1][0].s << "\n";*/
return ans;
}
void process(int l, int r) {
FOR(i,l,r+1) {
pi cur = {change[i][1],change[i][2]};
if (cedge.count(cur)) {
cedge.erase(cur);
tedge.insert(cur);
}
}
genDSU();
FOR(i,l,r+1) {
pi cur = {change[i][1],change[i][2]};
// cout << "HUH " << i << " " << cur.f << " " << cur.s << "\n";
if (change[i][0] == 0) tedge.insert(cur);
else tedge.erase(cur);
for (auto a: tri[i]) ans[a.s] = solve(a.f);
}
for (auto a: tedge) cedge.insert(a);
tedge.clear();
}
vi simulateCollapse(int n, vi T, vi X, vi Y, vi W, vi P) {
N = n;
F0R(i,sz(X)) {
if (X[i] > Y[i]) swap(X[i],Y[i]);
change.pb({T[i],X[i],Y[i]});
}
ans.resize(sz(W));
F0R(i,sz(ans)) tri[W[i]].pb({P[i],i});
for (int i = 0; i < sz(X); i += BLOCK) process(i,min(i+BLOCK,sz(X))-1);
return ans;
}
#ifdef LOCAL
int main(int argc, char *argv[]) {
int N, C, Q;
scanf("%d%d%d", &N, &C, &Q);
std::vector<int> T(C), X(C), Y(C);
for(int i = 0; i < C; i++) {
scanf("%d%d%d", &T[i], &X[i], &Y[i]);
}
std::vector<int> W(Q), P(Q);
for(int i = 0; i < Q; i++) {
scanf("%d%d", &W[i], &P[i]);
}
auto res = simulateCollapse(N, T, X, Y, W, P);
for(auto i : res) {
printf("%d\n", i);
}
}
#endif
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
Compilation message
collapse.cpp: In function 'int main(int, char**)':
collapse.cpp:203:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &C, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:206:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &T[i], &X[i], &Y[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:210:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &W[i], &P[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
/tmp/ccxe7Rhq.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc2gM4KX.o:collapse.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
