| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 255929 |
2020-08-02T05:56:38 Z |
IgorI |
Collapse (JOI18_collapse) |
C++17 |
|
1120 ms |
59368 KB |
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int N = 302020;
int n;
vector<int> cuts;
int root[N], sz[N];
int comp;
void Reset()
{
for (int i = 0; i < n; i++) root[i] = i, sz[i] = 1;
cuts.clear();
comp = n;
}
int Root(int x)
{
if (x == root[x]) return root[x];
return Root(root[x]);
}
void Merge(int v, int u)
{
v = Root(v), u = Root(u);
if (v == u) return;
comp--;
if (sz[v] < sz[u])
{
cuts.push_back(v);
sz[u] += sz[v];
root[v] = u;
}
else
{
cuts.push_back(u);
sz[v] += sz[u];
root[u] = v;
}
}
void Cut()
{
int x = cuts.back();
cuts.pop_back();
sz[root[x]] -= sz[x];
root[x] = x;
comp++;
}
int v[N], u[N], L[N], R[N], ans[N], z[N], it[N];
vector<pair<int, pair<int, int> > > on_left[N];
vector<pair<int, pair<int, int> > > on_right[N];
void solve(int le, int ri, int gap_le, int gap_ri)
{
if (le + 1 == ri)
{
if (v[le] == -1)
{
int ss = cuts.size();
for (int i = gap_le + 1; i <= z[le]; i++)
{
for (auto e : on_left[i])
{
if (e.second.first <= it[le] && it[le] < e.second.second)
{
Merge(e.first, i);
}
}
}
for (int i = gap_ri - 1; i > z[le]; i--)
{
for (auto e : on_right[i])
{
if (e.second.first <= it[le] && it[le] < e.second.second)
{
Merge(i, e.first);
}
}
}
ans[le] = comp;
while (cuts.size() != ss) Cut();
}
return;
}
int mi = (le + ri) / 2;
int ss = cuts.size();
for (int i = le; i < mi; i++)
{
if (v[i] != -1 && R[i] != -1 && ri <= R[i]) Merge(v[i], u[i]);
}
solve(mi, ri, gap_le, gap_ri);
while (cuts.size() != ss) Cut();
for (int i = ri - 1; i >= mi; i--)
{
if (v[i] != -1 && L[i] != -1 && L[i] < le) Merge(v[i], u[i]);
}
solve(le, mi, gap_le, gap_ri);
while (cuts.size() != ss) Cut();
}
void DCP(vector<int> x, vector<int> y, vector<pair<int, int> > &t, vector<int> p, int gap_le, int gap_ri)
{
Reset();
map<pair<int, int>, int> open;
int T = 0;
int j = 0;
for (int i = 0; i < x.size(); i++)
{
if (y[i] <= gap_le || gap_ri <= x[i])
{
if (open.find({x[i], y[i]}) == open.end())
{
open[{x[i], y[i]}] = T;
v[T] = x[i];
u[T] = y[i];
T++;
}
else
{
int z = open[{x[i], y[i]}];
L[T] = z;
L[z] = -1;
R[T] = -1;
R[z] = T;
v[T] = x[i];
u[T] = y[i];
open.erase({x[i], y[i]});
T++;
}
}
while (j < t.size() && i == t[j].first)
{
v[T] = -1, u[T] = -1;
it[T] = t[j].first;
z[T] = p[j];
T++;
j++;
}
}
solve(0, T, gap_le, gap_ri);
j = 0;
for (int i = 0; i < T; i++)
{
if (v[i] == -1)
{
t[j].first = ans[i];
j++;
}
}
}
void solve_queries(int gap_le, int gap_ri, vector<int> x, vector<int> y, vector<int> w, vector<int> p, vector<int> &answer)
{
vector<pair<int, int> > times;
for (int i = 0; i < w.size(); i++)
{
if (gap_le <= p[i] && p[i] < gap_ri)
{
times.push_back({w[i], i});
}
}
sort(times.begin(), times.end());
vector<int> mp(times.size());
for (int i = 0; i < times.size(); i++)
{
mp[i] = p[times[i].second];
}
DCP(x, y, times, mp, gap_le, gap_ri);
for (int i = 0; i < times.size(); i++)
{
answer[times[i].second] = times[i].first;
}
}
const int K = 2000;
vector<int> simulateCollapse(int n0, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p)
{
n = n0;
int c = t.size();
int q = w.size();
set<pair<int, int> > s;
for (int i = 0; i < c; i++)
{
if (x[i] > y[i]) swap(x[i], y[i]);
if (s.find({x[i], y[i]}) == s.end())
{
s.insert({x[i], y[i]});
}
else
{
s.erase({x[i], y[i]});
}
}
while (s.size())
{
pair<int, int> d = *(s.begin());
s.erase(s.begin());
x.push_back(d.first);
y.push_back(d.second);
c++;
}
map<pair<int, int>, int> mm;
for (int i = 0; i < c; i++)
{
if (mm.find({x[i], y[i]}) == mm.end())
{
mm[{x[i], y[i]}] = i;
}
else
{
int z = mm[{x[i], y[i]}];
mm.erase({x[i], y[i]});
on_left[y[i]].push_back({x[i], {z, i}});
on_right[x[i]].push_back({y[i], {z, i}});
}
}
vector<int> answer(q);
vector<int> pleft(n);
vector<int> pright(n);
for (int i = 1; i < n; i++)
{
pleft[i] = pleft[i - 1] + on_left[i].size();
}
for (int i = n - 2; i >= 0; i--)
{
pright[i] = pright[i + 1] + on_right[i].size();
}
vector<pair<int, int> > e;
int GL = 0;
while (GL != n - 1)
{
int okay = GL + 1;
for (int HF = GL + 1; HF < n; HF++)
{
if (pleft[HF - 1] - pleft[GL] <= K && pright[GL + 1] - pright[HF] <= K)
okay = HF;
}
e.push_back({GL, okay});
GL = okay;
}
assert(e.size() <= 40);
for (auto ee : e)
{
solve_queries(ee.first, ee.second, x, y, w, p, answer);
}
return answer;
}
#ifdef LOCAL
int main()
{
int n, c, q;
cin >> n >> c >> q;
vector<int> t(c), x(c), y(c), w(q), p(q);
for (int i = 0; i < c; i++)
{
cin >> t[i] >> x[i] >> y[i];
}
for (int i = 0; i < q; i++)
{
cin >> w[i] >> p[i];
}
vector<int> ans = simulateCollapse(n, t, x, y, w, p);
for (int i = 0; i < q; i++)
{
cout << ans[i] << "\n";
}
}
#endif // LOCAL
Compilation message
collapse.cpp: In function 'void solve(int, int, int, int)':
collapse.cpp:91:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (cuts.size() != ss) Cut();
~~~~~~~~~~~~^~~~~
collapse.cpp:102:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (cuts.size() != ss) Cut();
~~~~~~~~~~~~^~~~~
collapse.cpp:108:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (cuts.size() != ss) Cut();
~~~~~~~~~~~~^~~~~
collapse.cpp: In function 'void DCP(std::vector<int>, std::vector<int>, std::vector<std::pair<int, int> >&, std::vector<int>, int, int)':
collapse.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size(); i++)
~~^~~~~~~~~~
collapse.cpp:141:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < t.size() && i == t[j].first)
~~^~~~~~~~~~
collapse.cpp: In function 'void solve_queries(int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>&)':
collapse.cpp:165:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < w.size(); i++)
~~^~~~~~~~~~
collapse.cpp:174:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < times.size(); i++)
~~^~~~~~~~~~~~~~
collapse.cpp:179:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < times.size(); i++)
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
15232 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14848 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14848 KB |
Output is correct |
| 4 |
Correct |
12 ms |
14848 KB |
Output is correct |
| 5 |
Correct |
23 ms |
15232 KB |
Output is correct |
| 6 |
Correct |
59 ms |
15668 KB |
Output is correct |
| 7 |
Correct |
32 ms |
14976 KB |
Output is correct |
| 8 |
Correct |
49 ms |
14976 KB |
Output is correct |
| 9 |
Correct |
71 ms |
15360 KB |
Output is correct |
| 10 |
Correct |
92 ms |
15480 KB |
Output is correct |
| 11 |
Correct |
132 ms |
15864 KB |
Output is correct |
| 12 |
Correct |
119 ms |
15908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
21100 KB |
Output is correct |
| 2 |
Correct |
70 ms |
21100 KB |
Output is correct |
| 3 |
Correct |
296 ms |
28860 KB |
Output is correct |
| 4 |
Correct |
71 ms |
21100 KB |
Output is correct |
| 5 |
Correct |
1120 ms |
29160 KB |
Output is correct |
| 6 |
Correct |
451 ms |
22684 KB |
Output is correct |
| 7 |
Runtime error |
238 ms |
59368 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
20972 KB |
Output is correct |
| 2 |
Correct |
65 ms |
20972 KB |
Output is correct |
| 3 |
Correct |
65 ms |
21100 KB |
Output is correct |
| 4 |
Correct |
86 ms |
21100 KB |
Output is correct |
| 5 |
Correct |
320 ms |
21256 KB |
Output is correct |
| 6 |
Correct |
702 ms |
20160 KB |
Output is correct |
| 7 |
Runtime error |
194 ms |
52264 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
15232 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14848 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14848 KB |
Output is correct |
| 4 |
Correct |
12 ms |
14848 KB |
Output is correct |
| 5 |
Correct |
23 ms |
15232 KB |
Output is correct |
| 6 |
Correct |
59 ms |
15668 KB |
Output is correct |
| 7 |
Correct |
32 ms |
14976 KB |
Output is correct |
| 8 |
Correct |
49 ms |
14976 KB |
Output is correct |
| 9 |
Correct |
71 ms |
15360 KB |
Output is correct |
| 10 |
Correct |
92 ms |
15480 KB |
Output is correct |
| 11 |
Correct |
132 ms |
15864 KB |
Output is correct |
| 12 |
Correct |
119 ms |
15908 KB |
Output is correct |
| 13 |
Correct |
49 ms |
21100 KB |
Output is correct |
| 14 |
Correct |
70 ms |
21100 KB |
Output is correct |
| 15 |
Correct |
296 ms |
28860 KB |
Output is correct |
| 16 |
Correct |
71 ms |
21100 KB |
Output is correct |
| 17 |
Correct |
1120 ms |
29160 KB |
Output is correct |
| 18 |
Correct |
451 ms |
22684 KB |
Output is correct |
| 19 |
Runtime error |
238 ms |
59368 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Halted |
0 ms |
0 KB |
- |
