oj.uz

Submission #272816

# Submission time Handle Problem Language Result Execution time Memory
272816 2020-08-18T15:47:33 Z limabeans Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 28752 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;
}


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]});
    }
    vector<line> v;
    for (int i=0; i<n; i++) {
	v.push_back({T[i],X[i],Y[i]});
    }

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6016 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5280 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 11 ms 5888 KB Output is correct
6 Correct 248 ms 6648 KB Output is correct
7 Correct 54 ms 5248 KB Output is correct
8 Correct 54 ms 5368 KB Output is correct
9 Correct 61 ms 5980 KB Output is correct
10 Correct 108 ms 6136 KB Output is correct
11 Correct 447 ms 6776 KB Output is correct
12 Correct 407 ms 6776 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8940 KB Output is correct
2 Correct 53 ms 9344 KB Output is correct
3 Correct 167 ms 24044 KB Output is correct
4 Correct 64 ms 9464 KB Output is correct
5 Correct 352 ms 24300 KB Output is correct
6 Correct 4665 ms 11216 KB Output is correct
7 Execution timed out 15050 ms 28752 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8940 KB Output is correct
2 Correct 51 ms 9088 KB Output is correct
3 Correct 71 ms 9464 KB Output is correct
4 Correct 77 ms 9592 KB Output is correct
5 Correct 532 ms 9720 KB Output is correct
6 Correct 4920 ms 11564 KB Output is correct
7 Execution timed out 15033 ms 23108 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6016 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5280 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 11 ms 5888 KB Output is correct
6 Correct 248 ms 6648 KB Output is correct
7 Correct 54 ms 5248 KB Output is correct
8 Correct 54 ms 5368 KB Output is correct
9 Correct 61 ms 5980 KB Output is correct
10 Correct 108 ms 6136 KB Output is correct
11 Correct 447 ms 6776 KB Output is correct
12 Correct 407 ms 6776 KB Output is correct
13 Correct 43 ms 8940 KB Output is correct
14 Correct 53 ms 9344 KB Output is correct
15 Correct 167 ms 24044 KB Output is correct
16 Correct 64 ms 9464 KB Output is correct
17 Correct 352 ms 24300 KB Output is correct
18 Correct 4665 ms 11216 KB Output is correct
19 Execution timed out 15050 ms 28752 KB Time limit exceeded
20 Halted 0 ms 0 KB -