| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 603387 |
2022-07-24T05:57:05 Z |
장태환(#8428) |
Collapse (JOI18_collapse) |
C++17 |
|
82 ms |
60364 KB |
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
int uf[100100];
int siz[100100];
int rb[100100][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)
{
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;
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();
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++)
{
cq.push_back({q[j][k].first,j});
ai[cq.size() - 1] = q[j][k].second;
}
}
for (treeN = 1; treeN < cq.size(); treeN *= 2);
for (j = 1; j < 2 * treeN; j++)
{
stree[j].clear();
}
sort(cq.begin(), cq.end());
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]+1,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])]];
}
}
return rans;
}
Compilation message
collapse.cpp: In function 'void odc(int, int, int, int)':
collapse.cpp:45: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]
45 | for (j = 0; j < stree[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~~
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:106:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (i = 0; i < T.size(); i++)
| ~~^~~~~~~~~~
collapse.cpp:117:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for (i = 0; i < P.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 < T.size(); i += bc)
| ~~^~~~~~~~~~
collapse.cpp:142: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]
142 | for (k = 0; k < q[j].size(); k++)
| ~~^~~~~~~~~~~~~
collapse.cpp:148: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]
148 | for (treeN = 1; treeN < cq.size(); treeN *= 2);
| ~~~~~~^~~~~~~~~~~
collapse.cpp:154:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (j = 0; j < T.size(); j++)
| ~~^~~~~~~~~~
collapse.cpp:166: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]
166 | for (j = 0; j < cq.size(); j++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
27804 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
27596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
60316 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
82 ms |
60364 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
27804 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
27596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
