| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 603410 |
2022-07-24T06:23:35 Z |
장태환(#8428) |
Collapse (JOI18_collapse) |
C++17 |
|
15000 ms |
155108 KB |
#include "collapse.h"
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
int uf[100100];
int siz[100100];
int rb[10000100][2];
int c;
vector<pair<int, int>>stree[1 << 20];
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;
int f(int n)
{
while (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][0] = n;
rb[c][1] = n;
c++;
uf[n] = uf[m];
return 1;
}
int ans[100100];
int tgt[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)
{
int v= u(q1[j], q2[j]);
rbc += v;
p -= v;
}
}
ans[s] = p;
T:
p += rbc;
while (rbc--)
{
c--;
uf[rb[c][0]] = rb[c][1];
}
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][0]] = rb[c][1];
}
}
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
) {
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)
{
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 = 1000;
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:46: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]
46 | for (j = 0; j < stree[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~~
collapse.cpp:54: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]
54 | 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:111:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (i = 0; i < T.size(); i++)
| ~~^~~~~~~~~~
collapse.cpp:122:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (i = 0; i < P.size(); i++)
| ~~^~~~~~~~~~
collapse.cpp:127:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (i = 0; i < T.size(); i += bc)
| ~~^~~~~~~~~~
collapse.cpp:148: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]
148 | for (k = 0; k < q[j].size(); k++)
| ~~^~~~~~~~~~~~~
collapse.cpp:154: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]
154 | for (j = 0; j < ccq.size(); j++)
| ~~^~~~~~~~~~~~
collapse.cpp:159: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]
159 | for (treeN = 1; treeN < cq.size(); treeN *= 2);
| ~~~~~~^~~~~~~~~~~
collapse.cpp:164:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for (j = 0; j < T.size(); j++)
| ~~^~~~~~~~~~
collapse.cpp:176: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]
176 | for (j = 0; j < cq.size(); j++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
27732 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
27648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
33840 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
34192 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
33728 KB |
Output is correct |
| 2 |
Correct |
63 ms |
33768 KB |
Output is correct |
| 3 |
Correct |
60 ms |
34052 KB |
Output is correct |
| 4 |
Correct |
71 ms |
34288 KB |
Output is correct |
| 5 |
Correct |
653 ms |
34148 KB |
Output is correct |
| 6 |
Correct |
624 ms |
33260 KB |
Output is correct |
| 7 |
Correct |
4333 ms |
86468 KB |
Output is correct |
| 8 |
Correct |
8662 ms |
119876 KB |
Output is correct |
| 9 |
Correct |
57 ms |
35348 KB |
Output is correct |
| 10 |
Correct |
675 ms |
36012 KB |
Output is correct |
| 11 |
Correct |
7756 ms |
155108 KB |
Output is correct |
| 12 |
Execution timed out |
15046 ms |
96992 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
27732 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
27648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
