| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1049041 |
2024-08-08T12:27:24 Z |
n1k |
Werewolf (IOI18_werewolf) |
C++17 |
|
768 ms |
524288 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct seg{
int lb=0, rb=0;
ll sum=0;
seg *l=nullptr, *r=nullptr;
void ext(){
if(not l and lb!=rb){
int mb = (lb+rb)/2;
l = new seg{lb, mb}, r = new seg{mb+1, rb};
}
}
void upd(int x, ll val){
if(not(lb<=x and x<=rb)) return;
if(lb==rb){
sum += val;
}else{
ext();
l->upd(x, val);
r->upd(x, val);
sum = l->sum + r->sum;
}
}
ll qry(int lo, int hi){
if(hi<lb or rb < lo){
return 0;
}
if(lo <= lb and rb <= hi){
return sum;
}
ext();
return l->qry(lo, hi) + r->qry(lo, hi);
}
};
struct seg2d{
int lx=0, rx=0, ly=0, ry=0;
seg tree;
seg2d *l=nullptr, *r=nullptr;
void ext(){
if(not l and lx!=rx){
int mb = (lx+rx)/2;
l = new seg2d{lx, mb, ly, ry, seg{ly, ry}}, r = new seg2d{mb+1, rx, ly, ry, seg{ly, ry}};
}
}
void upd(int x, int y, ll val){
if(not(lx<=x and x<=rx)) return;
if(lx <= x and x <= rx){
tree.upd(y, val);
}
ext();
if(l){
l->upd(x, y, val);
r->upd(x, y, val);
}
}
ll qry(int lox, int hix, int loy, int hiy){
if(hix<lx or rx < lox){
return 0;
}
if(lox <= lx and rx <= hix){
return tree.qry(loy, hiy);
}
ext();
return l->qry(lox, hix, loy, hiy) + r->qry(lox, hix, loy, hiy);
}
};
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int Q = S.size();
int M = X.size();
std::vector<int> A(Q);
auto calc = [&](vector<array<int, 3>> e){
int t = N;
vector<vector<int>> g(2*N+5);
vector<int> p(2*N+5, -1);
auto find = [&](auto find, int u){
if(p[u]==-1) return u;
return p[u]=find(find, p[u]);
};
auto join = [&](int u, int v){
int a = find(find, u), b = find(find, v);
if(a!=b){
g[t].push_back(a);
g[t].push_back(b);
p[a]=t;
p[b]=t;
t++;
}
};
for(auto [cost, u, v]:e){
join(u, v);
}
vector<int> order(N);
int num = 0;
auto dfs = [&](auto dfs, int u) -> void {
for(int v:g[u]){
dfs(dfs, v);
}
if(u<N)
order[u]=num++;
};
dfs(dfs, t-1);
return order;
};
vector<array<int, 2>> ivx(Q), ivy(Q);
auto calcinterval = [&](vector<array<int, 3>> e, vector<int> order){
int t = N;
vector<int> p(N);
vector<array<int, 2>> mask(N);
for(int i=0; i<N; i++) {
mask[i][0]=mask[i][1]=order[i];
p[i]=i;
}
auto find = [&](auto find, int u){
if(p[u]==u) return u;
return p[u]=find(find, p[u]);
};
auto join = [&](int u, int v){
int a = find(find, u), b = find(find, v);
if(a!=b){
p[a] = b;
mask[b][0] = min(mask[b][0], mask[a][0]);
mask[b][1] = max(mask[b][1], mask[a][1]);
}
};
vector<array<int, 2>> todo;
for(int i=0; i<Q; i++){
todo.push_back({L[i], i});
}
sort(todo.begin(), todo.end());
for(auto [cost, u, v]:e){
while(todo.size() and todo.back()[0] > cost){
auto [l, id]=todo.back();
todo.pop_back();
ivx[id] = mask[find(find, S[id])];
}
join(u, v);
}
while(todo.size()){
auto [l, id]=todo.back();
todo.pop_back();
ivx[id] = mask[find(find, S[id])];
}
};
auto calcinterval2 = [&](vector<array<int, 3>> e, vector<int> order){
int t = N;
vector<int> p(N, -1);
vector<array<int, 2>> mask(N);
for(int i=0; i<N; i++) {
mask[i][0]=mask[i][1]=order[i];
p[i]=i;
}
auto find = [&](auto find, int u){
if(p[u]==u) return u;
return p[u]=find(find, p[u]);
};
auto join = [&](int u, int v){
int a = find(find, u), b = find(find, v);
if(a!=b){
p[a] = b;
mask[b][0] = min(mask[b][0], mask[a][0]);
mask[b][1] = max(mask[b][1], mask[a][1]);
}
};
vector<array<int, 2>> todo;
for(int i=0; i<Q; i++){
todo.push_back({R[i], i});
}
sort(todo.begin(), todo.end());
reverse(todo.begin(), todo.end());
for(auto [cost, u, v]:e){
while(todo.size() and todo.back()[0] < cost){
auto [r, id]=todo.back();
todo.pop_back();
ivy[id] = mask[find(find, E[id])];
}
join(u, v);
}
while(todo.size()){
auto [r, id]=todo.back();
todo.pop_back();
ivy[id] = mask[find(find, E[id])];
}
};
vector<array<int, 3>> ex, ey;
for(int i=0; i<M; i++){
ex.push_back({min(X[i], Y[i]), X[i], Y[i]});
ey.push_back({max(X[i], Y[i]), X[i], Y[i]});
}
sort(ex.begin(), ex.end());
reverse(ex.begin(), ex.end());
sort(ey.begin(), ey.end());
auto x = calc(ex);
auto y = calc(ey);
calcinterval(ex, x);
calcinterval2(ey, y);
seg2d tree = {0, N-1, 0, N-1, seg{0, N-1}};
for(int i=0; i<N; i++){
tree.upd(x[i], y[i], 1);
}
for(int i=0; i<Q; i++){
auto [x1, x2] = ivx[i];
auto [y1, y2] = ivy[i];
if(S[i]==8 and E[i]==41 and L[i]==0 and R[i]==41){
cout << ivx[i][0] << " " << ivx[i][1] << endl;
cout << ivy[i][0] << " " << ivy[i][1] << endl;
}
A[i] = tree.qry(x1, x2, y1, y2) > 0;
}
/*
cout<<endl;
for(int i=0; i<N; i++) cout << i << " " << x[i] << endl;
cout<<endl;
for(int i=0; i<N; i++) cout << i << " " << y[i] << endl;
cout<<endl;
for(int i=0; i<Q; i++) cout << ivx[i][0] << " " << ivx[i][1] << endl;
cout<<endl;
for(int i=0; i<Q; i++) cout << ivy[i][0] << " " << ivy[i][1] << endl;
*/
return A;
}
Compilation message
werewolf.cpp: In lambda function:
werewolf.cpp:120:13: warning: unused variable 't' [-Wunused-variable]
120 | int t = N;
| ^
werewolf.cpp: In lambda function:
werewolf.cpp:163:13: warning: unused variable 't' [-Wunused-variable]
163 | int t = N;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
768 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
