| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 255902 |
2020-08-02T05:12:52 Z |
IgorI |
Collapse (JOI18_collapse) |
C++17 |
|
15000 ms |
17384 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] = 0;
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];
void solve(int le, int ri)
{
if (le + 1 == ri)
{
if (v[le] == -1)
{
ans[le] = comp;
}
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);
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);
while (cuts.size() != ss) Cut();
}
void DCP(vector<int> x, vector<int> y, vector<pair<int, int> > &t, int z)
{
Reset();
map<pair<int, int>, int> open;
int T = 0;
int j = 0;
for (int i = 0; i < x.size(); i++)
{
if (y[i] <= z || z + 1 <= 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;
T++;
j++;
}
}
#ifdef LOCAL
cout << "<> T = " << T << endl;
for (int i = 0; i < T; i++)
{
cout << v[i] << " " << u[i] << " " << L[i] << " " << R[i] << endl;
}
#endif // LOCAL
solve(0, T);
j = 0;
for (int i = 0; i < T; i++)
{
if (v[i] == -1)
{
t[j].first = ans[i];
j++;
}
}
}
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++;
}
vector<int> answer(q);
int z = p[0];
vector<pair<int, int> > times(q);
for (int i = 0; i < q; i++)
{
times[i] = {w[i], i};
}
sort(times.begin(), times.end());
DCP(x, y, times, z);
for (int i = 0; i < q; i++)
{
answer[times[i].second] = times[i].first;
}
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)':
collapse.cpp:77:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (cuts.size() != ss) Cut();
~~~~~~~~~~~~^~~~~
collapse.cpp:83: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> >&, int)':
collapse.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size(); i++)
~~^~~~~~~~~~
collapse.cpp:116:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < t.size() && i == t[j].first)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
768 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
4728 KB |
Output is correct |
| 2 |
Correct |
49 ms |
4728 KB |
Output is correct |
| 3 |
Correct |
110 ms |
10488 KB |
Output is correct |
| 4 |
Correct |
44 ms |
4984 KB |
Output is correct |
| 5 |
Correct |
136 ms |
10872 KB |
Output is correct |
| 6 |
Correct |
58 ms |
6392 KB |
Output is correct |
| 7 |
Correct |
643 ms |
16232 KB |
Output is correct |
| 8 |
Correct |
122 ms |
11512 KB |
Output is correct |
| 9 |
Correct |
41 ms |
5888 KB |
Output is correct |
| 10 |
Correct |
47 ms |
5880 KB |
Output is correct |
| 11 |
Correct |
52 ms |
7032 KB |
Output is correct |
| 12 |
Correct |
130 ms |
12792 KB |
Output is correct |
| 13 |
Correct |
3219 ms |
14184 KB |
Output is correct |
| 14 |
Correct |
209 ms |
17384 KB |
Output is correct |
| 15 |
Execution timed out |
15036 ms |
17248 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
4728 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
4728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
768 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
