oj.uz

Submission #421528

# Submission time Handle Problem Language Result Execution time Memory
421528 2021-06-09T08:45:04 Z 송준혁(#7507) Collapse (JOI18_collapse) C++17
0 / 100
 15000 ms 14680 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=0; j<=W[i]; 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 12380 KB Output is correct
2 Incorrect 10 ms 12296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14500 KB Output is correct
2 Incorrect 55 ms 14612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14524 KB Output is correct
2 Correct 62 ms 14600 KB Output is correct
3 Correct 113 ms 14576 KB Output is correct
4 Correct 222 ms 14596 KB Output is correct
5 Correct 3733 ms 14680 KB Output is correct
6 Execution timed out 15102 ms 14384 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 12380 KB Output is correct
2 Incorrect 10 ms 12296 KB Output isn't correct
3 Halted 0 ms 0 KB -