# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
220725 |
2020-04-08T13:28:02 Z |
balbit |
Collapse (JOI18_collapse) |
C++14 |
|
15000 ms |
25972 KB |
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 998244353 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b) % mo;
}
const int maxn = 1e5+5;
const int BS = 100;
int state[maxn];
map<pii, int> mpid;
int ndel = 0; // Number of things that are connected
int ans[maxn], sz[maxn];
int par[maxn];
vector<int> stk;
int find(int x){
return x == par[x]?x:find(par[x]);
}
void setup(){
ndel = 0;
stk.clear();
for (int i = 0; i<maxn; ++i) par[i] = i, sz[i] = 1;
}
inline void undo(){
if (!stk.empty()) {
--ndel;
sz[par[stk.back()]] -= sz[stk.back()];
par[stk.back()] = stk.back();
stk.pop_back();
}
}
inline bool merge(int a, int b) {
a = find(a); b = find(b);
if (a == b) return 0;
++ndel;
if (sz[a] < sz[b]) {
swap(a,b);
}
stk.pb(b);
sz[a] += sz[b];
par[b] = a;
return 1;
}
vector<pii > g[maxn]; // to, time
vector<pii> quat[maxn]; // For this position, what time do I query and what id is it?
int itof[maxn];
int ID[maxn];
bool notsure[maxn];
void go(int n,vector<int> &TP,vector<int> &X,vector<int> &Y,vector<int> &W,vector<int> &P) {
// TP: query type, 0 is add, 1 is delete
// X,Y: Edge endpoints
// W: Query time
// P: Query position
// n: Length of the country
memset(itof, 0, sizeof itof);
int m = SZ(X), q = SZ(W);
// SQRT by Time
for (int t = 0; t<m; t += BS) {
int t2 = min(m, t+BS);
for (int i = t; i<t2; ++i) {
notsure[ID[i]] = 1;
}
setup();
for (int i = 0; i<n; ++i) {
for (pii x : g[i]) {
if (!notsure[x.s] && state[x.s]) {
merge(x.f,i);
}
}
while (itof[i] < SZ(quat[i]) && quat[i][itof[i]] .f < t2) {
int T = quat[i][itof[i]] .f, ansit = quat[i][itof[i]].s;
assert(T >= t && T < t2);
int nund = 0; // number of necessary undoes
for (int j = t; j<=T; ++j) {
state[ID[j]]^=1;
}
for (int j = t; j<t2; ++j) {
if (Y[j] <=i && state[ID[j]]) {
nund += merge(X[j], Y[j]);
}
}
for (int j = t; j<=T; ++j) {
state[ID[j]]^=1;
}
ans[ansit] += ndel;
++itof[i];
for (int cnt = 0; cnt < nund; ++cnt) undo();
}
}
for (int i = t; i<t2; ++i) {
state[ID[i]]^=1;
notsure[ID[i]] = 0;
}
}
}
vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P){
int q = SZ(P);
vector<pii> all;
for (int i = 0; i<SZ(X); ++i) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
all.pb({X[i], Y[i]});
}
SORT_UNIQUE(all);
for (int i = 0; i<SZ(X); ++i) {
ID[i] = lower_bound(ALL(all), make_pair(X[i], Y[i])) - all.begin();
}
{
set<pii> tmp;
for (int i = 0; i<SZ(X); ++i) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
if (!tmp.count({X[i], Y[i]})) {
g[Y[i]].pb({X[i], ID[i]});
tmp.insert({X[i], Y[i]});
}
}
for (int i = 0; i<SZ(P); ++i) {
quat[P[i]] .pb ({W[i], i});
}
for (int i = 0; i<n; ++i) {
sort(ALL(quat[i]));
}
go(n,T,X,Y,W,P);
}
for (int i = 0; i<q; ++i) bug(i,ans[i]);
for(int i = 0; i<n; ++i) g[i].clear(), quat[i].clear();
memset(state, 0, sizeof state);
for (int i = 0; i<SZ(X); ++i) {
X[i] = n-X[i] - 1;
Y[i] = n-Y[i] - 1;
}
for (int i = 0; i<SZ(P); ++i) {
P[i] = n-P[i] - 2;
}
{
set<pii> tmp;
for (int i = 0; i<SZ(X); ++i) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
if (!tmp.count({X[i], Y[i]})) {
g[Y[i]].pb({X[i],ID[i]});
tmp.insert({X[i], Y[i]});
}
}
for (int i = 0; i<SZ(P); ++i) {
quat[P[i]] .pb ({W[i], i});
}
for (int i = 0; i<n; ++i) {
sort(ALL(quat[i]));
}
go(n,T,X,Y,W,P);
}
vector<int> re(q);
for (int i = 0; i<q; ++i) {
bug(i, ans[i]);
re[i] = n-ans[i];
}
return re;
}
#ifdef BALBITe
signed main(){
IOS();
simulateCollapse(5,)
}
#endif
/*
4 4 9
0 0 2
0 1 3
0 2 3
1 2 3
1 0
1 1
1 2
2 0
2 1
2 2
3 0
3 1
3 2
*/
Compilation message
collapse.cpp: In function 'void go(int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
collapse.cpp:99:20: warning: unused variable 'q' [-Wunused-variable]
int m = SZ(X), q = SZ(W);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
6912 KB |
Output is correct |
2 |
Correct |
11 ms |
6784 KB |
Output is correct |
3 |
Correct |
13 ms |
6784 KB |
Output is correct |
4 |
Correct |
13 ms |
6912 KB |
Output is correct |
5 |
Correct |
29 ms |
7040 KB |
Output is correct |
6 |
Correct |
34 ms |
7260 KB |
Output is correct |
7 |
Correct |
10 ms |
6912 KB |
Output is correct |
8 |
Correct |
11 ms |
6912 KB |
Output is correct |
9 |
Correct |
37 ms |
7296 KB |
Output is correct |
10 |
Correct |
42 ms |
7292 KB |
Output is correct |
11 |
Correct |
52 ms |
7416 KB |
Output is correct |
12 |
Correct |
47 ms |
7544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
9708 KB |
Output is correct |
2 |
Correct |
66 ms |
10860 KB |
Output is correct |
3 |
Correct |
409 ms |
13416 KB |
Output is correct |
4 |
Correct |
109 ms |
10860 KB |
Output is correct |
5 |
Correct |
445 ms |
14696 KB |
Output is correct |
6 |
Correct |
187 ms |
11500 KB |
Output is correct |
7 |
Correct |
1141 ms |
20500 KB |
Output is correct |
8 |
Correct |
912 ms |
19944 KB |
Output is correct |
9 |
Correct |
51 ms |
11628 KB |
Output is correct |
10 |
Correct |
81 ms |
11628 KB |
Output is correct |
11 |
Correct |
204 ms |
12016 KB |
Output is correct |
12 |
Correct |
3601 ms |
21348 KB |
Output is correct |
13 |
Correct |
6274 ms |
22860 KB |
Output is correct |
14 |
Correct |
14022 ms |
24980 KB |
Output is correct |
15 |
Correct |
10129 ms |
25256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
9716 KB |
Output is correct |
2 |
Correct |
66 ms |
9840 KB |
Output is correct |
3 |
Correct |
82 ms |
10104 KB |
Output is correct |
4 |
Correct |
105 ms |
10104 KB |
Output is correct |
5 |
Correct |
174 ms |
9848 KB |
Output is correct |
6 |
Correct |
185 ms |
10800 KB |
Output is correct |
7 |
Correct |
828 ms |
17388 KB |
Output is correct |
8 |
Correct |
2809 ms |
22892 KB |
Output is correct |
9 |
Correct |
64 ms |
12920 KB |
Output is correct |
10 |
Correct |
260 ms |
13048 KB |
Output is correct |
11 |
Correct |
11735 ms |
25972 KB |
Output is correct |
12 |
Execution timed out |
15087 ms |
25376 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
6912 KB |
Output is correct |
2 |
Correct |
11 ms |
6784 KB |
Output is correct |
3 |
Correct |
13 ms |
6784 KB |
Output is correct |
4 |
Correct |
13 ms |
6912 KB |
Output is correct |
5 |
Correct |
29 ms |
7040 KB |
Output is correct |
6 |
Correct |
34 ms |
7260 KB |
Output is correct |
7 |
Correct |
10 ms |
6912 KB |
Output is correct |
8 |
Correct |
11 ms |
6912 KB |
Output is correct |
9 |
Correct |
37 ms |
7296 KB |
Output is correct |
10 |
Correct |
42 ms |
7292 KB |
Output is correct |
11 |
Correct |
52 ms |
7416 KB |
Output is correct |
12 |
Correct |
47 ms |
7544 KB |
Output is correct |
13 |
Correct |
43 ms |
9708 KB |
Output is correct |
14 |
Correct |
66 ms |
10860 KB |
Output is correct |
15 |
Correct |
409 ms |
13416 KB |
Output is correct |
16 |
Correct |
109 ms |
10860 KB |
Output is correct |
17 |
Correct |
445 ms |
14696 KB |
Output is correct |
18 |
Correct |
187 ms |
11500 KB |
Output is correct |
19 |
Correct |
1141 ms |
20500 KB |
Output is correct |
20 |
Correct |
912 ms |
19944 KB |
Output is correct |
21 |
Correct |
51 ms |
11628 KB |
Output is correct |
22 |
Correct |
81 ms |
11628 KB |
Output is correct |
23 |
Correct |
204 ms |
12016 KB |
Output is correct |
24 |
Correct |
3601 ms |
21348 KB |
Output is correct |
25 |
Correct |
6274 ms |
22860 KB |
Output is correct |
26 |
Correct |
14022 ms |
24980 KB |
Output is correct |
27 |
Correct |
10129 ms |
25256 KB |
Output is correct |
28 |
Correct |
44 ms |
9716 KB |
Output is correct |
29 |
Correct |
66 ms |
9840 KB |
Output is correct |
30 |
Correct |
82 ms |
10104 KB |
Output is correct |
31 |
Correct |
105 ms |
10104 KB |
Output is correct |
32 |
Correct |
174 ms |
9848 KB |
Output is correct |
33 |
Correct |
185 ms |
10800 KB |
Output is correct |
34 |
Correct |
828 ms |
17388 KB |
Output is correct |
35 |
Correct |
2809 ms |
22892 KB |
Output is correct |
36 |
Correct |
64 ms |
12920 KB |
Output is correct |
37 |
Correct |
260 ms |
13048 KB |
Output is correct |
38 |
Correct |
11735 ms |
25972 KB |
Output is correct |
39 |
Execution timed out |
15087 ms |
25376 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |