| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 603419 |
2022-07-24T06:35:55 Z |
장태환(#8428) |
Collapse (JOI18_collapse) |
C++17 |
|
4295 ms |
27592 KB |
#include "collapse.h"
#include <bits/stdc++.h>
#include <assert.h>
#pragma GCC optimize("Ofast")
using namespace std;
int uf[100100];
int siz[100100];
int rb[10000100];
int c;
vector<pair<int, int>>stree[1 << 18];
int q1[100100];
int q2[100100];
int ty[100100];
vector<pair<int, int>>cq;
vector<pair<int,int>>q[100100];
int treeN;
int sc, ec;
inline int f(int n)
{
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
n = uf[n];
return n;
}
int u(int n, int m)
{
n = f(n);
m = f(m);
if (n == m)
return 0;
if (siz[n] > siz[m])
swap(n, m);
siz[m] += siz[n];
rb[c] = n;
c++;
uf[n] = uf[m];
return 1;
}
int ans[100100];
int tgt[100100];
int ert[100100];
void odc(int p,int s=0, int e=treeN-1, int i=1)
{
int rbc = 0;
int j;
for (j = 0; j < stree[i].size(); j++)
{
int v= u(stree[i][j].first, stree[i][j].second);
p -= v;
rbc += v;
}
if (s == e)
{
if (cq.size() <= s)
goto T;
for (j = sc; j <= ec;j++)
{
if (ty[j]!=(j<=cq[s].second)&&((q1[j] <= cq[s].first) ^ (q2[j] > cq[s].first))&&tgt[j]<=cq[s].second&&ert[j]>cq[s].second)
{
int v= u(q1[j], q2[j]);
rbc += v;
p -= v;
}
}
ans[s] = p;
T:
p += rbc;
while (rbc--)
{
c--;
uf[rb[c]] = rb[c];
}
return;
}
odc(p,s, (s + e) / 2, i * 2);
odc(p,(s + e) / 2 + 1, e, i * 2 + 1);
p += rbc;
while (rbc--)
{
c--;
uf[rb[c]] = rb[c];
}
}
void pu(int qs, int qe, pair<int,int>va, int s = 0, int e = treeN - 1, int i = 1)
{
if (qs > qe || s > qe || qs > e)
return;
if (qs <= s && e <= qe)
{
stree[i].push_back(va);
return;
}
pu(qs, qe, va, s, (s + e) / 2, i * 2);
pu(qs, qe, va, (s + e) / 2 + 1, e, i * 2 + 1);
}
int ct[100100];
int rct[100100];
int ai[100100];
map<pair<int, int>, int>r;
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> P
) {
memset(ert, 10, sizeof(ert));
vector<int>rans(W.size());
int i;
for (i = 0; i < T.size(); i++)
{
ty[i] = T[i];
q1[i] = min(X[i], Y[i]);
q2[i] = max(X[i], Y[i]);
if (ty[i] == 1)
{
ert[r[make_pair(q1[i], q2[i])]] = i;
tgt[i] = r[make_pair(q1[i], q2[i])];
}
r[make_pair(q1[i], q2[i])] = i;
}
for (i = 0; i < P.size(); i++)
{
q[W[i]].push_back({ P[i],i });
}
int bc = 2000;
for (i = 0; i < T.size(); i += bc)
{
sc = i;
ec = min(i + bc - 1, (int)T.size() - 1);
int j;
for (j = 0; j < N; j++)
{
uf[j] = j;
siz[j] = 1;
}
cq.clear();
vector<pair<pair<int, int>,int>>ccq;
for (j = sc; j <= ec; j++)
{
if (ty[j] == 1)
{
ct[r[make_pair(q1[j], q2[j])]] = 0;
}
int k;
for (k = 0; k < q[j].size(); k++)
{
ccq.push_back({ {q[j][k].first,j},q[j][k].second });
}
}
sort(ccq.begin(), ccq.end());
for (j = 0; j < ccq.size(); j++)
{
cq.push_back(ccq[j].first);
ai[j] = ccq[j].second;
}
for (treeN = 1; treeN < cq.size(); treeN *= 2);
for (j = 1; j < 2 * treeN; j++)
{
stree[j].clear();
}
for (j = 0; j < T.size(); j++)
{
if (ct[r[make_pair(q1[j], q2[j])]])
{
int sp = lower_bound(cq.begin(), cq.end(), make_pair(q1[j],0)) - cq.begin();
int ep = lower_bound(cq.begin(), cq.end(), make_pair(q2[j], 0)) - cq.begin();
pu(0, sp - 1, make_pair(q1[j], q2[j]));
pu(ep, (int)cq.size() - 1, make_pair(q1[j], q2[j]));
}
}
if(cq.size())
odc(N);
for (j = 0; j < cq.size(); j++)
{
rans[ai[j]] = ans[j];
}
for (j = sc; j <= ec; j++)
{
rct[r[make_pair(q1[j], q2[j])]] = !ty[j];
ct[r[make_pair(q1[j], q2[j])]] = rct[r[make_pair(q1[j], q2[j])]];
}
assert(c == 0);
}
return rans;
}
Compilation message
collapse.cpp: In function 'void odc(int, int, int, int)':
collapse.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (j = 0; j < stree[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~~
collapse.cpp:72:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | if (cq.size() <= s)
| ~~~~~~~~~~^~~~
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:130:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for (i = 0; i < T.size(); i++)
| ~~^~~~~~~~~~
collapse.cpp:142:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (i = 0; i < P.size(); i++)
| ~~^~~~~~~~~~
collapse.cpp:147:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (i = 0; i < T.size(); i += bc)
| ~~^~~~~~~~~~
collapse.cpp:168: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]
168 | for (k = 0; k < q[j].size(); k++)
| ~~^~~~~~~~~~~~~
collapse.cpp:174:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for (j = 0; j < ccq.size(); j++)
| ~~^~~~~~~~~~~~
collapse.cpp:179:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | for (treeN = 1; treeN < cq.size(); treeN *= 2);
| ~~~~~~^~~~~~~~~~~
collapse.cpp:184:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for (j = 0; j < T.size(); j++)
| ~~^~~~~~~~~~
collapse.cpp:196:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for (j = 0; j < cq.size(); j++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
9812 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9580 KB |
Output is correct |
| 3 |
Correct |
8 ms |
9644 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9608 KB |
Output is correct |
| 5 |
Correct |
49 ms |
9736 KB |
Output is correct |
| 6 |
Incorrect |
136 ms |
10648 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
15740 KB |
Output is correct |
| 2 |
Correct |
42 ms |
16068 KB |
Output is correct |
| 3 |
Correct |
1044 ms |
18348 KB |
Output is correct |
| 4 |
Correct |
102 ms |
16360 KB |
Output is correct |
| 5 |
Correct |
1771 ms |
19176 KB |
Output is correct |
| 6 |
Correct |
1945 ms |
14996 KB |
Output is correct |
| 7 |
Incorrect |
4295 ms |
27592 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
15684 KB |
Output is correct |
| 2 |
Correct |
57 ms |
15720 KB |
Output is correct |
| 3 |
Correct |
82 ms |
15996 KB |
Output is correct |
| 4 |
Correct |
111 ms |
16176 KB |
Output is correct |
| 5 |
Incorrect |
807 ms |
16172 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
9812 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9580 KB |
Output is correct |
| 3 |
Correct |
8 ms |
9644 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9608 KB |
Output is correct |
| 5 |
Correct |
49 ms |
9736 KB |
Output is correct |
| 6 |
Incorrect |
136 ms |
10648 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
