| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 548371 |
2022-04-13T07:30:02 Z |
cig32 |
Werewolf (IOI18_werewolf) |
C++17 |
|
4000 ms |
139472 KB |
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>
//#include "werewolf.h"
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);
struct edge {
int f, t, w;
};
class cmp1 { // MST for wolf
public:
bool operator() (edge x, edge y) {
return x.w > y.w;
}
};
class cmp2 { // MST for human
public:
bool operator() (edge x, edge y) {
return x.w < y.w;
}
};
std::priority_queue<edge, std::vector<edge>, cmp1> wolf;
std::priority_queue<edge, std::vector<edge>, cmp2> human;
const int MAXN = 2e5 + 12;
int dsu1[MAXN], dsu2[MAXN];
int set_of1(int u) {
if(dsu1[u] == u) return u;
return dsu1[u] = set_of1(dsu1[u]);
}
int set_of2(int u) {
if(dsu2[u] == u) return u;
return dsu2[u] = set_of2(dsu2[u]);
}
void union1(int u, int v) {
dsu1[set_of1(u)] = set_of1(v);
}
void union2(int u, int v) {
dsu2[set_of2(u)] = set_of2(v);
}
int rep1[MAXN];
int rep2[MAXN];
std::vector<int> krt_wolf[2 * MAXN];
std::vector<int> krt_human[2 * MAXN];
int wlim_wolf[2 * MAXN];
int wlim_human[2 * MAXN];
int assigned[MAXN];
int stoN;
int q;
int mi[2 * MAXN], ma[2 * MAXN];
int par_wolf[19][2 * MAXN];
int wolfdepth[2 * MAXN];
std::pair<int, int> dfs1(int node, int curdepth) {
wolfdepth[node] = curdepth;
if(node < stoN) {
assigned[node] = q++;
mi[node] = ma[node] = assigned[node];
return {assigned[node], assigned[node]};
}
mi[node] = 1e9, ma[node] = -1;
for(int x: krt_wolf[node]) {
std::pair<int, int> res = dfs1(x, curdepth + 1);
mi[node] = std::min(mi[node], res.first);
ma[node] = std::max(ma[node], res.second);
par_wolf[0][x] = node;
}
return {mi[node], ma[node]};
}
int par_human[19][2 * MAXN];
int A[MAXN];
int humandepth[2 * MAXN];
int rangel[2 * MAXN], ranger[2 * MAXN];
std::pair<int, int> dfs2(int node, int curdepth) {
humandepth[node] = curdepth;
if(node < stoN) {
A[q] = assigned[node];
rangel[node] = ranger[node] = q;
q++;
return {rangel[node], ranger[node]};
}
rangel[node] = 1e9, ranger[node] = -1;
for(int x: krt_human[node]) {
std::pair<int, int> res = dfs2(x, curdepth + 1);
rangel[node] = std::min(rangel[node], res.first);
ranger[node] = std::max(ranger[node], res.second);
par_human[0][x] = node;
}
return {rangel[node], ranger[node]};
}
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) {
stoN = N;
for(int i=0; i<N; i++) {
dsu1[i] = dsu2[i] = i;
rep1[i] = rep2[i] = i;
wlim_wolf[i] = wlim_human[i] = i; //idk anymore
}
int Q = S.size();
std::vector<int> Answer(Q);
int M = X.size();
for(int i=0; i<M; i++) {
wolf.push({X[i], Y[i], std::max(X[i], Y[i])});
human.push({X[i], Y[i], std::min(X[i], Y[i])});
}
int newnode = N;
while(wolf.size()) {
if(set_of1(wolf.top().f) != set_of1(wolf.top().t)) {
int ff = rep1[set_of1(wolf.top().f)];
int tt = rep1[set_of1(wolf.top().t)];
union1(wolf.top().f, wolf.top().t);
krt_wolf[newnode].push_back(ff);
krt_wolf[newnode].push_back(tt);
wlim_wolf[newnode] = wolf.top().w;
rep1[set_of1(wolf.top().f)] = newnode;
newnode++;
}
wolf.pop();
}
int wolfrt = newnode - 1;
newnode = N;
while(human.size()) {
if(set_of2(human.top().f) != set_of2(human.top().t)) {
int ff = rep2[set_of2(human.top().f)];
int tt = rep2[set_of2(human.top().t)];
union2(human.top().f, human.top().t);
krt_human[newnode].push_back(ff);
krt_human[newnode].push_back(tt);
wlim_human[newnode] = human.top().w;
rep2[set_of2(human.top().f)] = newnode;
newnode++;
}
human.pop();
}
int humanrt = newnode - 1;
dfs1(wolfrt, 0);
par_wolf[0][wolfrt] = wolfrt;
for(int i=1; i<19; i++) {
for(int j=0; j<=wolfrt; j++) {
par_wolf[i][j] = par_wolf[i-1][par_wolf[i-1][j]];
}
}
q = 0;
dfs2(humanrt, 0);
par_human[0][humanrt] = humanrt;
for(int i=1; i<19; i++) {
for(int j=0; j<=humanrt; j++) {
par_human[i][j] = par_human[i-1][par_human[i-1][j]];
}
}
/*
std::cout << "wolf\n";
for(int i=wolfrt; i >= 0; i--) {
std::cout << "node "<<i<<". weight limit = "<<wlim_wolf[i]<<", node new ids range = [" << mi[i] << ", " << ma[i] << "]\n";
for(int x: krt_wolf[i]) std::cout << i << ' ' << x << '\n';
}
std::cout << "human\n";
for(int i=humanrt; i >= 0; i--) {
std::cout << "node " <<i<<". weight limit = "<<wlim_human[i]<<"\n";
for(int x: krt_human[i]) std::cout << i << ' ' << x << '\n';
}
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(assigned[j] == i) {
std::cout << "order " << i <<": " << j <<"\n";
}
}
}
*/
/*
std::cout << "A array:";
for(int i=0; i<N; i++) std::cout << " " << A[i];
std::cout << "\n";
*/
for(int i=0; i<Q; i++) {
for(int j=18; j>=0; j--) {
if(humandepth[S[i]] >= (1 << j) && wlim_human[par_human[j][S[i]]] >= L[i]) S[i] = par_human[j][S[i]];
if(wolfdepth[E[i]] >= (1 << j) && wlim_wolf[par_wolf[j][E[i]]] <= R[i]) E[i] = par_wolf[j][E[i]];
}
int l = mi[E[i]];
int r = ma[E[i]];
int humanl = rangel[S[i]];
int humanr = ranger[S[i]];
/*
std::cout << "query "<<i<<": ";
std::cout<<S[i]<<" "<<E[i]<<" ";
std::cout << "human array range [" << humanl << ", " << humanr << "] see see if any element in [" << l << ", " << r << "], ";
*/
//int res = wlt.upper_bound(humanl, humanr, r + 1);
int res = -1;
for(int i = humanl; i <= humanr; i++) {
if(A[i] <= r) res = std::max(res, A[i]);
}
/*
std::cout << "res=" << res<<"\n";
*/
if(res != -1 && l <= res && res <= r) {
Answer[i] = 1;
}
else {
Answer[i] = 0;
}
}
return Answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19412 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19412 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19412 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19412 KB |
Output is correct |
| 5 |
Correct |
11 ms |
19428 KB |
Output is correct |
| 6 |
Correct |
11 ms |
19496 KB |
Output is correct |
| 7 |
Correct |
10 ms |
19412 KB |
Output is correct |
| 8 |
Correct |
10 ms |
19492 KB |
Output is correct |
| 9 |
Correct |
10 ms |
19412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19412 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19412 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19412 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19412 KB |
Output is correct |
| 5 |
Correct |
11 ms |
19428 KB |
Output is correct |
| 6 |
Correct |
11 ms |
19496 KB |
Output is correct |
| 7 |
Correct |
10 ms |
19412 KB |
Output is correct |
| 8 |
Correct |
10 ms |
19492 KB |
Output is correct |
| 9 |
Correct |
10 ms |
19412 KB |
Output is correct |
| 10 |
Correct |
23 ms |
21204 KB |
Output is correct |
| 11 |
Correct |
19 ms |
21204 KB |
Output is correct |
| 12 |
Correct |
14 ms |
21040 KB |
Output is correct |
| 13 |
Correct |
19 ms |
21292 KB |
Output is correct |
| 14 |
Correct |
16 ms |
21248 KB |
Output is correct |
| 15 |
Correct |
21 ms |
21284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
597 ms |
131620 KB |
Output is correct |
| 2 |
Execution timed out |
4018 ms |
139472 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19412 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19412 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19412 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19412 KB |
Output is correct |
| 5 |
Correct |
11 ms |
19428 KB |
Output is correct |
| 6 |
Correct |
11 ms |
19496 KB |
Output is correct |
| 7 |
Correct |
10 ms |
19412 KB |
Output is correct |
| 8 |
Correct |
10 ms |
19492 KB |
Output is correct |
| 9 |
Correct |
10 ms |
19412 KB |
Output is correct |
| 10 |
Correct |
23 ms |
21204 KB |
Output is correct |
| 11 |
Correct |
19 ms |
21204 KB |
Output is correct |
| 12 |
Correct |
14 ms |
21040 KB |
Output is correct |
| 13 |
Correct |
19 ms |
21292 KB |
Output is correct |
| 14 |
Correct |
16 ms |
21248 KB |
Output is correct |
| 15 |
Correct |
21 ms |
21284 KB |
Output is correct |
| 16 |
Correct |
597 ms |
131620 KB |
Output is correct |
| 17 |
Execution timed out |
4018 ms |
139472 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
