| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 603457 |
2022-07-24T07:13:59 Z |
조영욱(#8429) |
Collapse (JOI18_collapse) |
C++17 |
|
38 ms |
12884 KB |
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
int sp;
typedef pair<int,int> P;
typedef pair<P,int> Pi;
set<Pi> s;
int n,c,q;
const int sz=131072;
vector<int> query[sz];
vector<int> ret;
int p[100000];
vector<P> seg[sz*2];
stack<P> st;
int find(int a) {
return p[a]<0?a:find(p[a]);
}
bool merge(int a,int b) {
a=find(a);
b=find(b);
if (a==b) {
return false;
}
if (-p[a]<=-p[b]) {
swap(a,b);
}
if (p[a]==p[b]) {
st.push(P(a,p[a]));
p[a]=p[a]-1;
}
st.push(P(b,p[b]));
p[b]=a;
return true;
}
void ins(int l,int r,P e,int node=1,int nodel=0,int noder=sz-1) {
if (r<nodel||l>noder) {
return;
}
if (l<=nodel&&noder<=r) {
seg[node].push_back(e);
return;
}
int mid=(nodel+noder)/2;
ins(l,r,e,node*2,nodel,mid);
ins(l,r,e,node*2+1,mid+1,noder);
}
void dfs(int node,int val) {
int now=val;
int got=st.size();
//printf("%d\n",node);
for(int i=0;i<seg[node].size();i++) {
//printf("%d\n",node);
//printf("%d %d\n",seg[node][i].first,seg[node][i].second);
if (merge(seg[node][i].first,seg[node][i].second)) {
now--;
}
}
if (node>=sz) {
for(int i=0;i<query[node-sz].size();i++) {
int ind=query[node-sz][i];
ret[ind]=now;
}
//exit(0);
return;
}
dfs(node*2,now);
dfs(node*2+1,now);
while (got<st.size()) {
assert(st.top().first>=0);
assert(st.top().first<n);
p[st.top().first]=st.top().second;
st.pop();
}
}
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> pp
) {
//st.push(P(-1,-1));
sp=pp[0];
n=N;
c=T.size();
q=pp.size();
ret.resize(q);
memset(p,-1,sizeof(p));
for(int i=0;i<c;i++) {
if (X[i]>Y[i]) {
swap(X[i],Y[i]);
}
if (X[i]<=sp&&Y[i]>sp) {
continue;
}
else {
}
if (T[i]==0) {
s.insert(Pi(P(X[i],Y[i]),i));
}
else {
auto iter=s.lower_bound(Pi(P(X[i],Y[i]),-1));
int got=(*iter).second;
s.erase(iter);
ins(got,i,P(X[i],Y[i]));
}
}
for(auto now:s) {
//printf(".%d %d\n",now.second,c-1);
ins(now.second,c-1,now.first);
}
for(int i=0;i<q;i++) {
query[W[i]].push_back(i);
}
dfs(1,n);
return ret;
}
Compilation message
collapse.cpp: In function 'void dfs(int, int)':
collapse.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=0;i<seg[node].size();i++) {
| ~^~~~~~~~~~~~~~~~~
collapse.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i=0;i<query[node-sz].size();i++) {
| ~^~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | while (got<st.size()) {
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
10196 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
10068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
12764 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
12884 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
12756 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
12756 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
10196 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
10068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
