| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 418821 |
2021-06-05T23:37:30 Z |
peuch |
Werewolf (IOI18_werewolf) |
C++17 |
|
347 ms |
134092 KB |
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 10;
int n;
int in[MAXN];
vector<int> ar[MAXN];
vector<int> ord;
vector<int> id;
pair<int, int> seg[4 * MAXN];
int cnt;
int freq[MAXN];
void build(int pos, int ini, int fim){
if(ini == fim){
seg[pos] = make_pair(ord[ini], ord[ini]);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
build(e, ini, mid);
build(d, mid + 1, fim);
seg[pos].first = max(seg[e].first, seg[d].first);
seg[pos].second = min(seg[e].second, seg[d].second);
}
pair<int, int> query(int pos, int ini, int fim, int p, int q){
cnt++;
if(ini > q || fim < p) return make_pair(-1, n + 1);
if(ini >= p && fim <= q) return seg[pos];
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
pair<int, int> eVal = query(e, ini, mid, p, q);
pair<int, int> dVal = query(d, mid + 1, fim, p, q);
pair<int, int> ret;
ret.first = max(eVal.first, dVal.first);
ret.second = min(eVal.second, dVal.second);
return ret;
}
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;
for(int i = 0; i < X.size(); i++){
ar[X[i]].push_back(Y[i]);
ar[Y[i]].push_back(X[i]);
in[X[i]]++;
in[Y[i]]++;
}
if(X.size() != N - 1) return vector<int> (E.size());
for(int i = 0; i < n; i++){
if(in[i] != 1) continue;
ord.clear();
int cur = i;
int pai = i;
do{
ord.push_back(cur);
freq[cur]++;
for(int i = 0; i < ar[cur].size(); i++){
int viz = ar[cur][i];
if(freq[viz] > 0) continue;
pai = cur;
cur = viz;
break;
}
}
while(in[cur] != 1);
break;
}
// printf("Iniciou\n");
// fflush(stdout);
id = vector<int> (n);
assert(ord.size() == n);
for(int i = 0; i < ord.size(); i++){
id[ord[i]] = i;
}
vector<int> ans(E.size());
build(1, 0, n - 1);
for(int i = 0; i < E.size(); i++){
int a = id[S[i]];
int b = id[E[i]];
if(a < b){
int ini = a, fim = b;
while(ini != fim){
int mid = (ini + fim) >> 1;
if(ini == fim - 1) mid = fim;
pair<int, int> qVal = query(1, 0, n - 1, a, mid);
if(qVal.second >= L[i]) ini = mid;
else fim = mid - 1;
}
pair<int, int> qVal = query(1, 0, n - 1, ini, b);
ans[i] = qVal.first <= R[i] && ini >= L[i] && ini <= R[i];
}
else{
int ini = b, fim = a;
while(ini != fim){
int mid = (ini + fim) >> 1;
if(ini == fim - 1) mid = fim;
pair<int, int> qVal = query(1, 0, n - 1, b, mid);
if(qVal.first <= R[i]) ini = mid;
else fim = mid - 1;
}
pair<int, int> qVal = query(1, 0, n - 1, ini, a);
ans[i] = qVal.second >= L[i] && ini >= L[i] && ini <= R[i];
}
// printf("%d\n", ans[i]);
}
// fprintf(stderr, "%d\n", cnt);
return ans;
}
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:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0; i < X.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp:49:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | if(X.size() != N - 1) return vector<int> (E.size());
| ~~~~~~~~~^~~~~~~~
werewolf.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0; i < ar[cur].size(); i++){
| ~~^~~~~~~~~~~~~~~~
werewolf.cpp:54:7: warning: variable 'pai' set but not used [-Wunused-but-set-variable]
54 | int pai = i;
| ^~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from werewolf.cpp:2:
werewolf.cpp:72:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | assert(ord.size() == n);
| ~~~~~~~~~~~^~~~
werewolf.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 0; i < ord.size(); i++){
| ~~^~~~~~~~~~~~
werewolf.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0; i < E.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
47180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
47180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
134092 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
47180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
