oj.uz

Submission #421533

# Submission time Handle Problem Language Result Execution time Memory
421533 2021-06-09T08:46:19 Z 송준혁(#7507) Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 16100 KB 
#include "collapse.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int M, P[101010], cnt;
vector<pii> E[404040], RB;
vector<int> Q[101010], ans;
map<pii, int> S;

int rt(int u){
	if (P[u] < 0) return u;
	return rt(P[u]);
}

void uni(int u, int v){
	u = rt(u), v = rt(v);
	if (u == v) return;
	if (P[u] > P[v]) swap(u, v);
	RB.pb(pii(u, P[u])), RB.pb(pii(v, P[v]));
	P[u] += P[v], P[v] = u;
	RB.pb(pii(-1,0)), cnt--;
}

void ins(int id, int s, int e, int ts, int te, pii t){
	if (e < ts || te < s) return;
	if (ts <= s && e <= te) {E[id].pb(t); return;}
	int m=s+e>>1;
	ins(id*2, s, m, ts, te, t);
	ins(id*2+1, m+1, e, ts, te, t);
}

void dnc(int id, int s, int e){
	int rb = RB.size();
	for (pii t : E[id]) uni(t.fi, t.se);
	if (s < e){
		int m=s+e>>1;
		dnc(id*2, s, m), dnc(id*2+1, m+1, e);
	}
	else for (int t : Q[s]) ans[t] = cnt;
	while (RB.size() > rb){
		pii t = RB.back(); RB.pop_back();
		if (t.fi >= 0) P[t.fi] = t.se;
		else cnt++;
	}
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> _P) {
	M = T.size();
	for (int i=0; i<W.size(); i++){
		for (int j=0; j<N; j++) P[j] = -1;
		cnt = N;
		RB.clear(), S.clear();
		for (int j=W[i]; j>=0; j--){
			if (X[j] > Y[j]) swap(X[j], Y[j]);
			if (T[j] == 1) S[pii(X[j], Y[j])] = 1;
			else{
				if (S[pii(X[j], Y[j])] == 1) continue;
				if (X[j]<=_P[i] && _P[i]<Y[j]) continue;
				uni(X[j], Y[j]);
			}
		}
		ans.pb(cnt);
	}
	/*
	for (int i=0; i<M; i++){
		if (X[i] > Y[i]) swap(X[i], Y[i]);
		if (X[i]<=_P[0] && _P[0]<Y[i]) continue;
		if (T[i] == 0) S[pii(X[i],Y[i])] = i;
		else{
			ins(1, 0, M-1, S[pii(X[i],Y[i])], i-1, pii(X[i],Y[i]));
			S[pii(X[i],Y[i])] = M;
		}
	}
	for (auto t : S) ins(1, 0, M-1, t.se, M-1, t.fi);
	ans.resize(W.size());
	for (int i=0; i<W.size(); i++) Q[W[i]].pb(i);
	for (int i=0; i<N; i++) P[i] = -1;
	cnt = N;
	dnc(1, 0, M-1);
	*/
	return ans;
}

Compilation message

collapse.cpp: In function 'void ins(int, int, int, int, int, pii)':
collapse.cpp:35:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int m=s+e>>1;
      |        ~^~
collapse.cpp: In function 'void dnc(int, int, int)':
collapse.cpp:44:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int m=s+e>>1;
      |         ~^~
collapse.cpp:48:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |  while (RB.size() > rb){
      |         ~~~~~~~~~~^~~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i=0; i<W.size(); i++){
      |                ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 12356 KB Output is correct
2 Correct 10 ms 12236 KB Output is correct
3 Correct 16 ms 12296 KB Output is correct
4 Correct 22 ms 12292 KB Output is correct
5 Correct 642 ms 12408 KB Output is correct
6 Correct 2938 ms 12772 KB Output is correct
7 Correct 13 ms 12364 KB Output is correct
8 Correct 15 ms 12316 KB Output is correct
9 Correct 1740 ms 12644 KB Output is correct
10 Correct 2115 ms 12712 KB Output is correct
11 Correct 2892 ms 12952 KB Output is correct
12 Correct 2860 ms 12940 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14532 KB Output is correct
2 Correct 54 ms 14524 KB Output is correct
3 Execution timed out 15019 ms 16100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14524 KB Output is correct
2 Correct 62 ms 14524 KB Output is correct
3 Correct 121 ms 14580 KB Output is correct
4 Correct 330 ms 14632 KB Output is correct
5 Correct 4733 ms 14796 KB Output is correct
6 Execution timed out 15074 ms 14244 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 12356 KB Output is correct
2 Correct 10 ms 12236 KB Output is correct
3 Correct 16 ms 12296 KB Output is correct
4 Correct 22 ms 12292 KB Output is correct
5 Correct 642 ms 12408 KB Output is correct
6 Correct 2938 ms 12772 KB Output is correct
7 Correct 13 ms 12364 KB Output is correct
8 Correct 15 ms 12316 KB Output is correct
9 Correct 1740 ms 12644 KB Output is correct
10 Correct 2115 ms 12712 KB Output is correct
11 Correct 2892 ms 12952 KB Output is correct
12 Correct 2860 ms 12940 KB Output is correct
13 Correct 38 ms 14532 KB Output is correct
14 Correct 54 ms 14524 KB Output is correct
15 Execution timed out 15019 ms 16100 KB Time limit exceeded
16 Halted 0 ms 0 KB -