oj.uz

Submission #67611

# Submission time Handle Problem Language Result Execution time Memory
67611 2018-08-15T06:33:39 Z top34051 Collapse (JOI18_collapse) C++17
30 / 100
 6450 ms 268888 KB 
//subtask3
#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
const int sq = 320;

class DSU {
public:
	int n,com;
	int head[maxn], sz[maxn];
	stack<pii> stk;

	void init(int _n) {
		n = com = _n;
		for(int i=0;i<n;i++) {
			head[i] = i;
			sz[i] = 1;
		}
	}

	int findhead(int x) {
		if(x==head[x]) return x;
		return findhead(head[x]);
	}

	void add_edge(int u, int v) {
		int x = findhead(u), y = findhead(v);
		if(sz[x] > sz[y]) swap(x,y);
		stk.push({x,y});
		if(x!=y) {
			head[x] = y;
			sz[y] += sz[x];
			com--;
		}
	}

	void pop_edge() {
		int x = stk.top().X, y = stk.top().Y; stk.pop();
		if(x!=y) {
            head[x] = x;
            sz[y] -= sz[x];
            com++;
		}
	}

	int size() {
	    return com;
	}
} dsu;

struct trp {
	int x,y,id;
};

int n,m,q;
vector<trp> op;
vector<int> alive;
vector<int> ask[maxn];
int ans[maxn];

bool cmpL(trp a, trp b) {
    if(a.y != b.y) return a.y < b.y;
    return a.id < b.id;
}

bool cmpR(trp a, trp b) {
    if(a.x != b.x) return a.x > b.x;
    return a.id < b.id;
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> D, vector<int> P) {
	n = N; m = T.size(); q = D.size();
	for(int i=0;i<m;i++) {
		if(X[i]>Y[i]) swap(X[i],Y[i]);
	}

	for(int i=0;i<q;i++) ask[D[i]].push_back(i);

	for(int s=0;s<m;s+=sq) {
		int e = min(m,s+sq-1);

		//---------------------------------------------------------------------------

		op.clear();
		for(int i=s;i<=e;i++) {
			for(auto x : ask[i]) op.push_back({P[x],P[x],x});
		}
		for(auto i : alive) op.push_back({X[i],Y[i],-1});

		sort(op.begin(),op.end(),cmpL);

		dsu.init(n);
		for(auto t : op) {
			int x = t.id;
			if(x<0) dsu.add_edge(t.x,t.y);
			else {
				int ex = 0;
				for(int i=s;i<=D[x];i++) {
					if(Y[i]<=t.x) {
						dsu.add_edge(X[i],Y[i]);
						ex++;
					}
				}
				ans[x] += dsu.size();
				while(ex--) dsu.pop_edge();
			}
		}

		//---------------------------------------------------------------------------

		op.clear();
		for(int i=s;i<=e;i++) {
			for(auto x : ask[i]) op.push_back({P[x]+1,P[x]+1,x});
		}
		for(auto i : alive) op.push_back({X[i],Y[i],-1});

		sort(op.begin(),op.end(),cmpR);

		dsu.init(n);
		for(auto t : op) {
			int x = t.id;
			if(x<0) dsu.add_edge(t.x,t.y);
			else {
				int ex = 0;
				for(int i=s;i<=D[x];i++) {
					if(t.y<=X[i]) {
						dsu.add_edge(X[i],Y[i]);
						ex++;
					}
				}
				ans[x] += dsu.size();
				while(ex--) dsu.pop_edge();
			}
		}

		//---------------------------------------------------------------------------

		for(int i=s;i<=e;i++) alive.push_back(i);

	}

	vector<int> vec;
	for(int i=0;i<q;i++) vec.push_back(ans[i]-n);
	return vec;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3832 KB Output is correct
2 Incorrect 8 ms 3832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7212 KB Output is correct
2 Incorrect 70 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7380 KB Output is correct
2 Correct 76 ms 7532 KB Output is correct
3 Correct 89 ms 7560 KB Output is correct
4 Correct 106 ms 7568 KB Output is correct
5 Correct 215 ms 7568 KB Output is correct
6 Correct 246 ms 7568 KB Output is correct
7 Correct 2735 ms 154940 KB Output is correct
8 Correct 5528 ms 267896 KB Output is correct
9 Correct 71 ms 267896 KB Output is correct
10 Correct 252 ms 267896 KB Output is correct
11 Correct 5315 ms 268688 KB Output is correct
12 Correct 6450 ms 268756 KB Output is correct
13 Correct 6071 ms 268888 KB Output is correct
14 Correct 6250 ms 268888 KB Output is correct
15 Correct 5647 ms 268888 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3832 KB Output is correct
2 Incorrect 8 ms 3832 KB Output isn't correct
3 Halted 0 ms 0 KB -