Submission #877761

#	Time	Username	Problem	Language	Result	Execution time	Memory
877761		8pete8	Werewolf (IOI18_werewolf)	C++14	0 / 100	1026 ms	266648 KiB

werewolf

#include "werewolf.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include <iomanip>  
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define ll long long    
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
const int mxn=1e6,lg=35;
struct kst{
  int pa[mxn+10],cnt=0,val[mxn+10],up[mxn+10][lg+5];
  pii mnmx[mxn+10];
  vector<int>adj[mxn+10],pos;
  void init(){for(int i=0;i<=mxn;i++)pa[i]=i;}
  int find(int u){return (pa[u]==u)?u:pa[u]=find(pa[u]);}
  void merg(int a,int b){
    cnt++;
    int u=find(a),v=find(b);
    adj[cnt].pb(u);
    pa[u]=cnt;
    if(u==v)return;
    adj[cnt].pb(v);
    pa[v]=cnt;
  }
  void dfs(int cur,int n){
    for(auto i:adj[cur])up[i][0]=cur,dfs(i,n),cout<<cur<<" "<<i<<'\n';
    if(cur<n)pos.pb(cur);
  }
  void dfs2(int cur){for(auto i:adj[cur])dfs2(i),mnmx[cur]={min(mnmx[cur].f,mnmx[i].f),max(mnmx[cur].s,mnmx[i].s)};}
  void upd(vector<ppii>e,int n){
    cnt=n-1;
    for(auto i:e)merg(i.s.f,i.s.s),val[cnt]=i.f;
    for(int i=0;i<n;i++)val[i]=i;
    dfs(cnt,n);
    for(int i=0;i<n;i++)mnmx[pos[i]]={i,i};
    for(int i=n;i<=cnt;i++)mnmx[i]={1e9,-1e9};
    for(int i=0;i<=lg;i++)up[cnt][i]=cnt;
    for(int j=1;j<=lg;j++)for(int i=0;i<=cnt;i++)up[i][j]=up[up[i][j-1]][j-1];
    dfs2(cnt);
  }
}k[2];
struct fen{
  int bit[mxn+10];
  void update(int pos,int n){for(int i=pos;i<=n;i+=(i&-i))bit[i]++;}
  int qry(int pos){
    int sum=0;
    for(int i=pos;i>0;i-=(i&-i))sum+=bit[i];
    return sum;
  }
}f;
vector<int> check_validity(int n,vector<int>x,vector<int>y,vector<int>st,vector<int>e,vector<int>l,vector<int>r){
  vector<ppii>g;
  for(int i=0;i<x.size();i++)g.pb({min(x[i],y[i]),{x[i],y[i]}});
  sort(rall(g));
  k[0].init();
  k[0].upd(g,n);
  g.clear();
  for(int i=0;i<x.size();i++)g.pb({max(x[i],y[i]),{x[i],y[i]}});
  sort(all(g));
  k[1].init();
  k[1].upd(g,n);
  int cur,cur2;
  vector<pair<pii,pii>>qry;
  for(int i=0;i<st.size();i++){
    cur=st[i];
    for(int j=lg;j>=0;j--)if(k[0].val[k[0].up[cur][j]]>=l[i])cur=k[0].up[cur][j];
    cur2=e[i];
    for(int j=lg;j>=0;j--)if(k[1].val[k[1].up[cur2][j]]<=r[i])cur2=k[1].up[cur2][j];
    qry.pb({{k[0].mnmx[cur].f,i+1},k[1].mnmx[cur2]});
    qry.pb({{k[0].mnmx[cur].s,-(i+1)},k[1].mnmx[cur2]});
  }
  vector<int>ans(st.size());
  sort(all(qry));
  int id,mul=1;
  cur=0;
  for(int i=0;i<qry.size();i++){
    if(qry[i].f.s>0)id=qry[i].f.s-1;
    else id=-(qry[i].f.s)-1;
    while(cur<=qry[i].f.f)f.update(k[1].mnmx[k[0].pos[cur]].f+1,n),cur++;
    if(qry[i].f.s>0)mul=-1;
    else mul=1;
    ans[id]+=((f.qry(qry[i].s.s+1)*mul)-(f.qry(qry[i].s.f)*mul));
  }
  for(auto &i:ans)i=!!i;
  return ans;
  /*
  range l1,r2 l2,r2
  find how many on from 1->l2-1,and 1->r2
  find on 1->x; for qry i;
  foreach qry l1,r1; sort(all) l1,r1
  to get x when l1,r1 is on is (1->x when r1)-(1->x when l1-1);
  */
}/*
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}
*/

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:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int i=0;i<x.size();i++)g.pb({min(x[i],y[i]),{x[i],y[i]}});
      |               ~^~~~~~~~~
werewolf.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i=0;i<x.size();i++)g.pb({max(x[i],y[i]),{x[i],y[i]}});
      |               ~^~~~~~~~~
werewolf.cpp:85:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i=0;i<st.size();i++){
      |               ~^~~~~~~~~~
werewolf.cpp:97:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int i=0;i<qry.size();i++){
      |               ~^~~~~~~~~~~

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