| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 421532 |
2021-06-09T08:46:06 Z |
송준혁(#7507) |
Collapse (JOI18_collapse) |
C++17 |
|
38 ms |
27596 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++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
24732 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
27588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
27596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
24732 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
