| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1076721 |
2024-08-26T15:53:05 Z |
NValchanov |
Colors (RMI18_colors) |
C++17 |
|
3000 ms |
77116 KB |
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
const int MAXM = 2e5 + 10;
int has[MAXN];
int wants[MAXN];
vector < int > have_color[MAXN];
vector < int > want_color[MAXN];
struct edge
{
int u, v;
edge()
{
u = 1;
v = 1;
}
edge(int _u, int _v)
{
if(_u > _v)
swap(_u, _v);
u = _u;
v = _v;
}
friend bool operator<(edge e1, edge e2)
{
if(e1.u != e2.u)
return e1.u < e2.u;
return e1.v < e2.v;
}
};
vector < edge > edges;
struct SegmentTree
{
struct DSU
{
int n, sz;
int leader[MAXN];
int sizes[MAXN];
stack < int > st;
void init(int _n)
{
n = _n;
sz = 0;
while(!st.empty())
st.pop();
for(int i = 1; i <= n; i++)
{
leader[i] = i;
sizes[i] = 1;
}
}
int size()
{
return sz;
}
int find_leader(int u)
{
return leader[u] == u ? u : find_leader(leader[u]);
}
bool connected(int u, int v)
{
return find_leader(u) == find_leader(v);
}
void unite(int u, int v)
{
u = find_leader(u);
v = find_leader(v);
if(u == v)
return;
if(sizes[u] < sizes[v])
swap(u, v);
sizes[u] += sizes[v];
leader[v] = u;
n--;
sz++;
st.push(v);
}
void rollback(int t)
{
while(st.size() > t)
{
int u = st.top();
st.pop();
n++;
sz--;
sizes[leader[u]] -= sizes[u];
leader[u] = u;
}
}
};
int n, m;
DSU dsu;
vector < edge > tree[4 * MAXN];
bool can[MAXN];
void clear(int left, int right, int idx)
{
tree[idx].clear();
if(left == right)
return;
int mid = left + (right - left) / 2;
clear(left, mid, 2 * idx);
clear(mid + 1, right, 2 * idx + 1);
}
void init(int _n, int _m)
{
n = _n;
m = _m;
dsu.init(n);
for(int i = 0; i <= m; i++)
{
can[i] = false;
}
clear(0, m, 1);
}
void update(int left, int right, int idx, int qleft, int qright, edge e)
{
if(qleft > qright)
return;
if(left > qright || right < qleft)
return;
if(qleft <= left && right <= qright)
{
tree[idx].push_back(e);
return;
}
int mid = left + (right - left) / 2;
update(left, mid, 2 * idx, qleft, qright, e);
update(mid + 1, right, 2 * idx + 1, qleft, qright, e);
}
void calc(int left, int right, int idx)
{
int t = dsu.size();
for(edge e : tree[idx])
{
dsu.unite(e.u, e.v);
}
if(left == right)
{
set < int > sources;
for(int u : have_color[left])
{
sources.insert(dsu.find_leader(u));
}
for(int u : want_color[left])
{
if(sources.find(dsu.find_leader(u)) != sources.end())
{
can[u] = true;
}
}
dsu.rollback(t);
return;
}
int mid = left + (right - left) / 2;
calc(left, mid, 2 * idx);
calc(mid + 1, right, 2 * idx + 1);
dsu.rollback(t);
}
void update(int from, int to, edge e)
{
update(0, m, 1, from, to, e);
}
void calc()
{
calc(0, m, 1);
}
bool query(int t)
{
return can[t];
}
};
int n, m;
SegmentTree st;
void init()
{
st.init(n, m);
for(int i = 1; i <= n; i++)
{
have_color[i].clear();
want_color[i].clear();
}
}
void read()
{
cin >> n >> m;
init();
for(int i = 1; i <= n; i++)
{
cin >> has[i];
have_color[has[i]].push_back(i);
}
for(int i = 1; i <= n; i++)
{
cin >> wants[i];
want_color[wants[i]].push_back(i);
}
for(int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
edges.push_back(edge(u, v));
}
}
void solve()
{
for(edge e : edges)
{
int from = max(wants[e.u], wants[e.v]);
int to = min(has[e.u], has[e.v]);
st.update(from, to, e);
}
st.calc();
}
void find_ans()
{
bool ans = true;
for(int i = 1; i <= n; i++)
{
ans &= st.query(i);
}
cout << ans << endl;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while(t--)
{
read();
solve();
find_ans();
}
return 0;
}
Compilation message
colors.cpp: In member function 'void SegmentTree::DSU::rollback(int)':
colors.cpp:109:29: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
109 | while(st.size() > t)
| ~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3027 ms |
42744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3060 ms |
77116 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3032 ms |
40584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3032 ms |
40584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3027 ms |
42744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3056 ms |
38692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2074 ms |
58328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3027 ms |
42744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
