| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 129327 |
2019-07-12T03:27:16 Z |
qkxwsm |
Collapse (JOI18_collapse) |
C++14 |
|
15000 ms |
32948 KB |
#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969
#define MAXN 100013
#define MAGIC 521
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, Q;
vi ans;
set<int> edges[MAXN], ins[MAXN], de[MAXN];
vector<array<int, 4> > events;
vector<array<int, 4> > block;
vi ord;
bool cmp(int a, int b)
{
return block[a][2] < block[b][2];
}
struct dsu
{
int dsu[MAXN], siz[MAXN];
void init()
{
FOR(i, 0, N)
{
dsu[i] = i;
siz[i] = 1;
}
}
int get(int u)
{
return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
bool merge(int u, int v)
{
u = get(u); v = get(v);
if (u == v) return false;
if (siz[u] > siz[v]) swap(u, v);
siz[v] += siz[u];
dsu[u] = v;
return true;
}
};
dsu D[2];
void proc()
{
D[0].init(); D[1].init();
FOR(i, 0, N)
{
ins[i] = edges[i];
}
FOR(i, 0, SZ(block))
{
if (block[i][1] == 1)
{
int u = block[i][2], v = block[i][3];
if (edges[v].find(u) != edges[v].end()) edges[v].erase(u);
}
}
FOR(i, 0, N)
{
set_difference(ALL(ins[i]), ALL(edges[i]), inserter(de[i], de[i].end()));
ins[i].clear();
}
int cp = -1, cc = 0;
ord.clear();
FOR(i, 0, SZ(block))
{
if (block[i][1] == 2) ord.PB(i);
}
sort(ALL(ord), cmp);
for (int idx : ord)
{
int t = block[idx][0], x = block[idx][2], qid = block[idx][3];
while(cp < x)
{
cp++; cc++;
for (int w : edges[cp]) if (D[0].merge(cp, w)) cc--;
}
FOR(j, 0, SZ(block))
{
if (block[j][0] > t) break;
if (block[j][1] == 2) continue;
int u = block[j][2], v = block[j][3];
if (ins[u].empty()) ins[u] = de[u];
if (ins[v].empty()) ins[v] = de[v];
}
// cerr << "cc = " << cc << endl;
int res = cc;
FOR(j, 0, SZ(block))
{
if (block[j][0] > t) break;
if (block[j][1] == 2) continue;
int u = block[j][2], v = block[j][3];
if (v > x) continue;
if (block[j][1] == 1)
{
if (ins[v].find(u) != ins[v].end()) ins[v].erase(u);
}
else
{
ins[v].insert(u);
}
}
FOR(j, 0, SZ(block))
{
if (block[j][0] > t) break;
if (block[j][1] == 2) continue;
int u = block[j][2], v = block[j][3];
if (v > x) continue;
for (int w : ins[v])
{
// cerr << "merge " << v << ' ' << w << endl;
if (D[1].merge(D[0].get(v), D[0].get(w))) res--;
}
ins[v].clear();
}
FOR(j, 0, SZ(block))
{
int u = block[j][2], v = block[j][3];
u = D[0].get(u);
D[1].dsu[u] = u; D[1].siz[u] = 1;
v = D[0].get(v);
D[1].dsu[v] = v; D[1].siz[v] = 1;
}
// cerr << res << endl;
ans[qid] += res;
}
FOR(i, 0, SZ(block))
{
if (block[i][1] == 2) continue;
int u = block[i][2], v = block[i][3];
if (block[i][1] == 1)
{
if (edges[v].find(u) != edges[v].end()) edges[v].erase(u);
}
else
{
edges[v].insert(u);
}
}
//build the set of edges now!
}
void solve()
{
//find # of cc's with value LESS THAN whatever
//sort all the queries in the block.
//after processing the block, the sets should store all active edges.
// FOR(i, 0, SZ(events))
// {
// assert(events[i][1] == 2 || events[i][2] < events[i][3]);
// }
for (int i = 0; i < SZ(events); i += MAGIC)
{
for (int j = i; j < SZ(events) && j < i + MAGIC; j++)
{
block.PB(events[j]);
}
proc();
block.clear();
}
}
vi simulateCollapse(int n, vi t, vi x, vi y, vi w, vi p)
{
N = n; Q = SZ(w);
ans.resize(Q);
FOR(i, 0, SZ(t))
{
if (x[i] > y[i]) swap(x[i], y[i]);
events.PB({i, t[i], x[i], y[i]});
}
FOR(i, 0, Q)
{
events.PB({w[i], 2, p[i], i});
}
sort(ALL(events));
FOR(i, 0, SZ(events))
{
events[i][0] = i;
}
// cerr << "SOLVE\n";
solve();
FOR(i, 0, N)
{
edges[i].clear();
ins[i].clear();
}
for (auto &e : events)
{
if (e[1] == 2)
{
e[2] = N - 2 - e[2];
}
else
{
e[2] = N - 1 - e[2];
e[3] = N - 1 - e[3];
swap(e[2], e[3]);
}
}
// cerr << "SOLVE\n";
solve();
return ans;
//i thnk i see how to do it!
//event: disconnect u -> v, connect u -> v, ask qid x pos y: so you store time, typ, who it happens to
return ans;
}
Compilation message
collapse.cpp: In function 'void proc()':
collapse.cpp:145:8: warning: unused variable 'u' [-Wunused-variable]
int u = block[j][2], v = block[j][3];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
15000 KB |
Output is correct |
| 2 |
Incorrect |
106 ms |
14712 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1855 ms |
18892 KB |
Output is correct |
| 2 |
Incorrect |
1971 ms |
18788 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1850 ms |
18840 KB |
Output is correct |
| 2 |
Correct |
2068 ms |
18864 KB |
Output is correct |
| 3 |
Correct |
2194 ms |
18792 KB |
Output is correct |
| 4 |
Correct |
2236 ms |
18796 KB |
Output is correct |
| 5 |
Correct |
2278 ms |
18840 KB |
Output is correct |
| 6 |
Correct |
2536 ms |
19632 KB |
Output is correct |
| 7 |
Correct |
7848 ms |
28800 KB |
Output is correct |
| 8 |
Correct |
12662 ms |
32236 KB |
Output is correct |
| 9 |
Correct |
2953 ms |
19952 KB |
Output is correct |
| 10 |
Correct |
4272 ms |
20064 KB |
Output is correct |
| 11 |
Execution timed out |
15036 ms |
32948 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
15000 KB |
Output is correct |
| 2 |
Incorrect |
106 ms |
14712 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
