oj.uz

Submission #272925

# Submission time Handle Problem Language Result Execution time Memory
272925 2020-08-18T19:59:34 Z limabeans Collapse (JOI18_collapse) C++17
35 / 100
 15000 ms 29328 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl


struct dsu0 {
    vector<int> par, siz;
    int n;
    int cc;
    int largest;
    void init(int n) {
	assert(n>0);
	this->n=n;
	cc=n;
	par.resize(n+10);siz.resize(n+10);
	for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
	largest=1;
    }
    int parent(int x) {
	assert(x>=0 && x<n);
	return par[x]==x?x:par[x]=parent(par[x]);
    }
    bool join(int x, int y) {
	x=parent(x);y=parent(y);
	if (x==y) return false;
	cc--;
	if (siz[x]<siz[y]) swap(x,y);
	siz[x]+=siz[y];par[y]=x;
	largest=max(largest,siz[x]);
	return true;
    }
};


using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e5 + 5;

struct line {
    int type, x, y;
    line(int _t, int _x, int _y) : type(_t), x(_x), y(_y) {}
};


set<int> g[maxn];
set<pair<int,int>> edges;


void add_edge(int x, int y) {
    if (x>y) swap(x,y);
    g[x].insert(y);
    g[y].insert(x);
    edges.insert({x,y});
}

void rem_edge(int x, int y) {
    if (x>y) swap(x,y);
    g[x].erase(y);
    g[y].erase(x);
    edges.erase({x,y});
}

vector<int> solve(int N, vector<line> v, vector<vector<pair<int,int>>> ev, int Q) {
    int n = v.size();
    vector<int> ans(Q);

    for (int i=0; i<n; i++) {
	if (v[i].type==0) {
	    add_edge(v[i].x,v[i].y);
	} else {
	    rem_edge(v[i].x,v[i].y);
	}

	for (auto qu: ev[i]) {
	    int id = qu.first;
	    int x = qu.second;
	    dsu0 dsu; dsu.init(N);
	    for (auto ed: edges) {
		int u = ed.first;
		int v = ed.second;
		if (u<=x && x+1<=v) continue;
		dsu.join(u,v);
	    }
	    ans[id] = dsu.cc;
	}
    }
    return ans;
}



struct dsu_rollback {
    int n;
    vector<int> par, siz;
    int cc;
    vector<pair<int,int>> undo;
    
    void init(int n) {
	this->n=n;
	par.resize(n);
	siz.resize(n);
	for (int i=0; i<n; i++) {
	    par[i]=i;
	    siz[i]=1;
	}
	cc = n;
    }
    int parent(int x) {
	while (par[x] != x) x=par[x];
	return x;
    }

    void join(int u, int v) {
	u = parent(u);
	v = parent(v);
	if (u != v) {
	    if (siz[u]<siz[v]) swap(u,v);
	    par[v]=u;
	    siz[u]+=siz[v];
	    cc--;
	}
	undo.push_back({u,v});
    }

    void rollback() {
	assert(undo.size());
	int u = undo.back().first;
	int v = undo.back().second;
	if (u!=v) {
	    siz[u]-=siz[v];
	    par[v]=v;
	    cc++;
	}
	undo.pop_back();
    }
};


const int SQ = 316; // sqrt(10^5) = 316.227

struct dat {
    int x, y, id;
    dat(int _x, int _y, int _id) : x(_x), y(_y), id(_id) {}
};



bool cmpY(dat A, dat B) {
    if (A.y != B.y) return A.y < B.y;
    return A.id < B.id;
}

bool cmpX(dat A, dat B) {
    if (A.x != B.x) return A.x > B.x;
    return A.id < B.id;
}

// All lines in v are addEdge(x,y)
// requests[time]: idx, loc
vector<int> solveTask3(int N, vector<line> v, vector<vector<pair<int,int>>> requests, int Q) {
    //cerr<<"task3"<<endl;
    int m = v.size();
    for (auto &line: v) {
	if (line.x>line.y) {
	    swap(line.x,line.y);
	}
    }
    vector<int> reqTime(Q);
    for (int i=0; i<m; i++) {
	for (auto p: requests[i]) reqTime[p.first] = i;
    }
    vector<int> ans(Q, -N);
    vector<int> alive;

    // iterate over sqrt blocks of time
    for (int i=0; i<m; i+=SQ) {
	int start = i; int end = min(i+SQ-1, m-1);
	// [start, end]
	vector<dat> op;

	// sort by increasing Y
	{
	    op.clear();
	    // add all alive graph edits
	    for (int idx: alive) {
		op.push_back({v[idx].x,v[idx].y,-1});
	    }
	    // add all relevant queries
	    for (int j=start; j<=end; j++) {
		for (auto p: requests[j]) {
		    op.push_back({p.second,p.second,p.first});
		}
	    }

	    
	    sort(op.begin(), op.end(), cmpY);
	    dsu_rollback dsu;
	    dsu.init(N);
	    for (auto o: op) {
		if (o.id < 0) {
		    dsu.join(o.x,o.y);
		} else {
		    int time = reqTime[o.id];
		    int did = 0;
		    for (int j=start; j<=time; j++) {
			if (v[j].y<=o.x) {
			    dsu.join(v[j].x,v[j].y);
			    did++;
			}
		    }
		    ans[o.id] += dsu.cc;
		    while (did--) {
			dsu.rollback();
		    }
		}
	    }
	}


	// sort by decreasing X
	{
	    op.clear();
	    // add all alive graph edits
	    for (int idx: alive) {
		op.push_back({v[idx].x,v[idx].y,-1});
	    }
	    // add all relevant queries
	    for (int j=start; j<=end; j++) {
		for (auto p: requests[j]) {
		    op.push_back({p.second+1,p.second+1,p.first});
		}
	    }

	    
	    sort(op.begin(), op.end(), cmpX);
	    dsu_rollback dsu;
	    dsu.init(N);
	    for (auto o: op) {
		if (o.id < 0) {
		    dsu.join(o.x,o.y);
		} else {
		    int time = reqTime[o.id];
		    int did = 0;
		    for (int j=start; j<=time; j++) {
			if (o.y<=v[j].x) {
			    dsu.join(v[j].x,v[j].y);
			    did++;
			}
		    }
		    ans[o.id] += dsu.cc;
		    while (did--) {
			dsu.rollback();
		    }
		}
	    }
	}


	// update alive
	for (int j=start; j<=end; j++) {
	    alive.push_back(j);
	}
    }

    return ans;
}



std::vector<int> simulateCollapse(
				  int N,
				  std::vector<int> T,
				  std::vector<int> X,
				  std::vector<int> Y,
				  std::vector<int> W,
				  std::vector<int> P
				  ) {

    int n = T.size();
    
    vector<vector<pair<int,int>>> ev(n);
    for (int i=0; i<(int)W.size(); i++) {
	ev[W[i]].push_back({i,P[i]});
    }

    bool t0 = true;
    vector<line> v;
    for (int i=0; i<n; i++) {
	v.push_back({T[i],X[i],Y[i]});
	if (T[i]==1) t0=false;
    }

    if (t0) return solveTask3(N, v, ev, W.size());

    return solve(N, v, ev, W.size());
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5888 KB Output is correct
2 Correct 5 ms 5248 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 7 ms 5376 KB Output is correct
5 Correct 10 ms 5888 KB Output is correct
6 Correct 28 ms 6132 KB Output is correct
7 Correct 6 ms 5376 KB Output is correct
8 Correct 56 ms 5368 KB Output is correct
9 Correct 60 ms 6008 KB Output is correct
10 Correct 108 ms 6136 KB Output is correct
11 Correct 33 ms 6204 KB Output is correct
12 Correct 33 ms 6204 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 11252 KB Output is correct
2 Correct 45 ms 9336 KB Output is correct
3 Correct 156 ms 24044 KB Output is correct
4 Correct 80 ms 11528 KB Output is correct
5 Correct 336 ms 24428 KB Output is correct
6 Correct 197 ms 11388 KB Output is correct
7 Correct 4257 ms 29328 KB Output is correct
8 Correct 2334 ms 25324 KB Output is correct
9 Correct 59 ms 12148 KB Output is correct
10 Execution timed out 15061 ms 10920 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 11252 KB Output is correct
2 Correct 70 ms 11136 KB Output is correct
3 Correct 79 ms 11424 KB Output is correct
4 Correct 103 ms 11656 KB Output is correct
5 Correct 215 ms 11144 KB Output is correct
6 Correct 242 ms 11340 KB Output is correct
7 Correct 2482 ms 23740 KB Output is correct
8 Correct 4804 ms 27796 KB Output is correct
9 Correct 71 ms 12012 KB Output is correct
10 Correct 304 ms 11956 KB Output is correct
11 Correct 4831 ms 28500 KB Output is correct
12 Correct 5790 ms 28080 KB Output is correct
13 Correct 4941 ms 28440 KB Output is correct
14 Correct 5735 ms 28588 KB Output is correct
15 Correct 4870 ms 28224 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5888 KB Output is correct
2 Correct 5 ms 5248 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 7 ms 5376 KB Output is correct
5 Correct 10 ms 5888 KB Output is correct
6 Correct 28 ms 6132 KB Output is correct
7 Correct 6 ms 5376 KB Output is correct
8 Correct 56 ms 5368 KB Output is correct
9 Correct 60 ms 6008 KB Output is correct
10 Correct 108 ms 6136 KB Output is correct
11 Correct 33 ms 6204 KB Output is correct
12 Correct 33 ms 6204 KB Output is correct
13 Correct 52 ms 11252 KB Output is correct
14 Correct 45 ms 9336 KB Output is correct
15 Correct 156 ms 24044 KB Output is correct
16 Correct 80 ms 11528 KB Output is correct
17 Correct 336 ms 24428 KB Output is correct
18 Correct 197 ms 11388 KB Output is correct
19 Correct 4257 ms 29328 KB Output is correct
20 Correct 2334 ms 25324 KB Output is correct
21 Correct 59 ms 12148 KB Output is correct
22 Execution timed out 15061 ms 10920 KB Time limit exceeded
23 Halted 0 ms 0 KB -