oj.uz

Submission #67606

# Submission time Handle Problem Language Result Execution time Memory
67606 2018-08-15T05:55:21 Z top34051 Collapse (JOI18_collapse) C++17
30 / 100
 6607 ms 271932 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> 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(int i=0;i<s;i++) 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(int i=0;i<s;i++) 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();
			}
		}
	}

	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 19 ms 3956 KB Output is correct
2 Incorrect 8 ms 3956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7708 KB Output is correct
2 Incorrect 73 ms 8388 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 57 ms 8688 KB Output is correct
2 Correct 75 ms 8688 KB Output is correct
3 Correct 94 ms 9160 KB Output is correct
4 Correct 113 ms 9692 KB Output is correct
5 Correct 198 ms 9896 KB Output is correct
6 Correct 264 ms 10584 KB Output is correct
7 Correct 2653 ms 157936 KB Output is correct
8 Correct 5282 ms 271112 KB Output is correct
9 Correct 75 ms 271112 KB Output is correct
10 Correct 292 ms 271112 KB Output is correct
11 Correct 5263 ms 271876 KB Output is correct
12 Correct 6147 ms 271932 KB Output is correct
13 Correct 5478 ms 271932 KB Output is correct
14 Correct 6607 ms 271932 KB Output is correct
15 Correct 5602 ms 271932 KB Output is correct

Subtask #4
0 / 35.0

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