| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 434133 |
2021-06-20T15:29:11 Z |
vanic |
Werewolf (IOI18_werewolf) |
C++14 |
|
1192 ms |
524292 KB |
#include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=2e5+5;
struct union_find{
int kad[maxn];
int parent[maxn];
int sz[maxn];
union_find(){
for(int i=0; i<maxn; i++){
parent[i]=i;
sz[i]=1;
kad[i]=0;
}
}
int find(int x, int vrij){
if(kad[x]>vrij || parent[x]==x){
return x;
}
return find(parent[x], vrij);
}
void update(int x, int y, int vrij){
x=find(x, vrij);
y=find(y, vrij);
if(sz[x]>sz[y]){
swap(x, y);
}
parent[x]=y;
sz[y]+=sz[x];
kad[x]=vrij;
}
bool query(int x, int y, int vrij){
return find(x, vrij)==find(y, vrij);
}
};
//int pos1[maxn], pos2[maxn];
vector < int > ms[maxn];
vector < int > s, e, l, r;
vector < int > sol;
int n;
/*
bool cmp1(int a, int b){
return l[a]>l[b];
}
bool cmp2(int a, int b){
return r[a]<r[b];
}
*/
union_find U1, U2;
void dodaj1(int x){
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i]<x){
if(!U1.query(x, ms[x][i], x+1)){
U1.update(x, ms[x][i], x+1);
}
}
}
}
void dodaj2(int x){
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i]>x){
if(!U2.query(x, ms[x][i], n-x)){
U2.update(x, ms[x][i], n-x);
}
}
}
}
vector < int > put;
int pos[maxn];
void dfs(int x, int prosl){
put.push_back(x);
for(int i=0; i<ms[x].size(); i++){
if(ms[x][i]!=prosl){
dfs(ms[x][i], x);
}
}
}
const int Log=18;
int binary2(int a, int pred, int vrij){
int b;
for(int i=Log-1; i>-1; i--){
b=a+pred*(1<<i);
if(b<0 || b>=n){
continue;
}
if(U2.query(put[a], put[b], vrij)){
a+=(1<<i)*pred;
}
}
return a;
}
int binary1(int a, int pred, int vrij){
int b;
for(int i=Log-1; i>-1; i--){
b=a+pred*(1<<i);
if(b<0 || b>=n){
continue;
}
if(U1.query(put[a], put[b], vrij)){
a+=(1<<i)*pred;
}
}
return a;
}
vector < int > check_validity(int N, vector < int > x, vector < int > y, vector < int > S, vector < int > E, vector < int > L, vector < int > R){
s=S;
e=E;
l=L;
r=R;
n=N;
int m=x.size();
for(int i=0; i<m; i++){
ms[x[i]].push_back(y[i]);
ms[y[i]].push_back(x[i]);
}
int q=s.size();
for(int i=0; i<n; i++){
dodaj1(i);
dodaj2(n-i-1);
}
int poc;
for(int i=0; i<n; i++){
if(ms[i].size()==1){
poc=i;
break;
}
}
dfs(poc, poc);
for(int i=0; i<n; i++){
pos[put[i]]=i;
}
int a, b;
for(int i=0; i<q; i++){
if(pos[s[i]]<pos[e[i]]){
a=binary2(pos[s[i]], 1, n-l[i]);
b=binary1(pos[e[i]], -1, r[i]+1);
if(a>=b){
sol.push_back(1);
}
else{
sol.push_back(0);
}
}
else{
a=binary2(pos[s[i]], -1, n-l[i]);
b=binary1(pos[e[i]], 1, r[i]+1);
if(a<=b){
sol.push_back(1);
}
else{
sol.push_back(0);
}
}
cout << a << ' ' << b << endl;
}
return sol;
}
Compilation message
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0; i<ms[x].size(); i++){
| ~^~~~~~~~~~~~~
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:145:5: warning: 'poc' may be used uninitialized in this function [-Wmaybe-uninitialized]
145 | dfs(poc, poc);
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
483 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
483 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1192 ms |
43676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
483 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
