oj.uz

Submission #421515

# Submission time Handle Problem Language Result Execution time Memory
421515 2021-06-09T08:36:45 Z 송준혁(#7507) Collapse (JOI18_collapse) C++17
30 / 100
 199 ms 30776 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<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:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for (int i=0; i<W.size(); i++) Q[W[i]].pb(i);
      |                ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12492 KB Output is correct
2 Incorrect 9 ms 12276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14992 KB Output is correct
2 Correct 45 ms 15104 KB Output is correct
3 Correct 105 ms 22288 KB Output is correct
4 Correct 35 ms 15300 KB Output is correct
5 Correct 126 ms 23452 KB Output is correct
6 Correct 42 ms 15812 KB Output is correct
7 Correct 193 ms 29020 KB Output is correct
8 Correct 141 ms 25112 KB Output is correct
9 Correct 39 ms 15300 KB Output is correct
10 Correct 37 ms 15380 KB Output is correct
11 Correct 41 ms 15780 KB Output is correct
12 Correct 157 ms 26308 KB Output is correct
13 Correct 199 ms 28708 KB Output is correct
14 Correct 183 ms 30776 KB Output is correct
15 Correct 198 ms 30592 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14988 KB Output is correct
2 Incorrect 36 ms 14988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12492 KB Output is correct
2 Incorrect 9 ms 12276 KB Output isn't correct
3 Halted 0 ms 0 KB -