| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 454286 |
2021-08-05T03:45:21 Z |
urd05 |
Werewolf (IOI18_werewolf) |
C++17 |
|
972 ms |
27420 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=262144;
typedef pair<int,int> P;
P seg[sz*2];
vector<int> adj[200000];
int ind[200000];
int rev[200000];
P merge(P a,P b) {
return P(min(a.first,b.first),max(a.second,b.second));
}
P sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
if (r<nodel||l>noder) {
return P(1e9,-1e9);
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return merge(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}
void update(int i,P val) {
i+=sz;
seg[i]=val;
while (i>1) {
i/=2;
seg[i]=merge(seg[i*2],seg[i*2+1]);
}
}
vector<int> check_validity(int n, vector<int> x,vector<int> y,vector<int> s,vector<int> e,vector<int> l,vector<int> r) {
int q =s.size();
int m=x.size();
for(int i=0;i<m;i++) {
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
int st=0;
for(int i=0;i<n;i++){
if(adj[i].size()==1) {
st=i;
break;
}
}
int prev=-1;
ind[0]=st;
for(int i=1;i<n;i++) {
for(int j=0;j<adj[st].size();j++) {
if (adj[st][j]!=prev) {
prev=st;
st=adj[st][j];
ind[i]=st;
break;
}
}
}
for(int i=0;i<sz*2;i++) {
seg[i]=P(1e9,-1e9);
}
for(int i=0;i<n;i++) {
seg[sz+i]=P(ind[i],ind[i]);
rev[ind[i]]=i;
}
for(int i=sz-1;i>0;i--) {
seg[i]=merge(seg[i*2],seg[i*2+1]);
}
vector<int> ret;
for(int i=0;i<q;i++) {
int st=rev[s[i]];
int en=rev[e[i]];
if (sum(min(st,en),max(st,en)).first>=l[i]) {
if (ind[en]<=r[i]) {
ret.push_back(1);
}
else {
ret.push_back(0);
}
continue;
}
if (st<=en) {
int lo=st-1;
int hi=en;
while (lo+1<hi) {
int mid=(lo+hi)/2;
if (sum(st,mid).first<l[i]) {
hi=mid;
}
else {
lo=mid;
}
}
if (lo==st-1||ind[lo]<l[i]||ind[lo]>r[i]) {
ret.push_back(0);
continue;
}
if (sum(hi,en).second<=r[i]) {
ret.push_back(1);
}
else {
ret.push_back(0);
}
}
else {
int lo=st;
int hi=en+1;
while (lo+1<hi) {
int mid=(lo+hi)/2;
if (sum(mid,en).first<l[i]) {
lo=mid;
}
else {
hi=mid;
}
}
if (hi==en+1||ind[hi]<l[i]||ind[hi]>r[i]) {
ret.push_back(0);
continue;
}
if (sum(st,lo).second<=r[i]) {
ret.push_back(1);
}
else {
ret.push_back(0);
}
}
}
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:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int j=0;j<adj[st].size();j++) {
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
972 ms |
27420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
