Submission #454286

#	Time	Username	Problem	Language	Result	Execution time	Memory
454286		urd05	Werewolf (IOI18_werewolf)	C++17	0 / 100	972 ms	27420 KiB

werewolf

#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 (stderr)

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++) {
      |                 ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51