| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 418769 |
2021-06-05T20:54:23 Z |
peuch |
Werewolf (IOI18_werewolf) |
C++17 |
|
4000 ms |
56096 KB |
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
struct event{
int l, r, id;
event(int _l = 0, int _r = 0, int _id = -1){
l = _l;
r = _r;
id = _id;
}
bool operator < (event a){
if(r == a.r) return id < a.id;
return r < a.r;
}
};
int n;
vector<int> rep, tam;
stack<int> pilha;
vector<pair<int, int> > seg[4 * MAXN];
void uni(int a, int b);
void rollback();
int find(int a);
void update(int pos, int ini, int fim, int p, int q, pair<int, int> val);
int query(int pos, int ini, int fim, int id, int x, int y);
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
n = N;
int q = L.size();
int m = X.size();
rep = vector<int> (n);
tam = vector<int> (n, 1);
for(int i = 0; i < n; i++)
rep[i] = i;
vector<int> ans(q);
vector<event> ord;
for(int i = 0; i < m; i++){
if(X[i] > Y[i]) swap(X[i], Y[i]);
update(1, 0, n - 1, 0, X[i], make_pair(X[i], Y[i]));
ord.push_back(event(X[i], Y[i]));
}
for(int i = 0; i < q; i++)
ord.push_back(event(L[i], R[i], i));
sort(ord.begin(), ord.end());
for(int i = 0; i < ord.size(); i++){
if(ord[i].id == -1)
update(1, 0, n - 1, 0, n - 1, make_pair(ord[i].l, ord[i].r));
else{
assert(pilha.empty());
ans[ord[i].id] = query(1, 0, n - 1, ord[i].l, S[ord[i].id], E[ord[i].id]);
}
}
return ans;
}
void uni(int a, int b){
a = find(a);
b = find(b);
if(a == b){
pilha.push(-1);
return;
}
if(tam[a] < tam[b]) swap(a, b);
pilha.push(b);
rep[b] = a;
tam[a] += tam[b];
}
void rollback(){
int a, b;
b = pilha.top();
pilha.pop();
if(b == -1) return;
a = rep[b];
tam[a] -= tam[b];
rep[b] = b;
}
int find(int a){
if(a == rep[a]) return a;
return find(rep[a]);
}
void update(int pos, int ini, int fim, int p, int q, pair<int, int> val){
if(ini > q || fim < p) return;
if(ini >= p && fim <= q){
seg[pos].push_back(val);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
update(e, ini, mid, p, q, val);
update(d, mid + 1, fim, p, q, val);
}
int query(int pos, int ini, int fim, int id, int x, int y){
for(int i = 0; i < seg[pos].size(); i++)
uni(seg[pos][i].first, seg[pos][i].second);
int ret;
if(ini == fim) ret = find(x) == find(y);
else{
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
if(id <= mid) ret = query(e, ini, mid, id, x, y);
else ret = query(d, mid + 1, fim, id, x, y);
}
for(int i = 0; i < seg[pos].size(); i++)
rollback();
return ret;
}
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0; i < ord.size(); i++){
| ~~^~~~~~~~~~~~
werewolf.cpp: In function 'int query(int, int, int, int, int, int)':
werewolf.cpp:104:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i = 0; i < seg[pos].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
werewolf.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0; i < seg[pos].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19020 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
19048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19020 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
19048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4064 ms |
56096 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19020 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
19048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
