Submission #726001

#	Time	Username	Problem	Language	Result	Execution time	Memory
726001		Cookie	Werewolf (IOI18_werewolf)	C++14	0 / 100	523 ms	160916 KiB

werewolf

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "werewolf.h"

namespace {

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

}  // namespace
const int mxn = 7e5;
int pl[mxn + 1], pr[mxn + 1], n;
vt<int>adj[mxn + 1], adjl[mxn + 1], adjr[mxn + 1];
vt<pii>ql[mxn + 1], qr[mxn + 1];

int tonodel[mxn + 1], tonoder[mxn + 1], tt = 0;
int tinl[mxn + 1], toutl[mxn + 1], tinr[mxn + 1], toutr[mxn + 1], rootl[mxn + 1], rootr[mxn + 1];
int fpl(int u){
    if(pl[u] == u)return(u);
    return(pl[u] = fpl(pl[u]));
}
int fpr(int u){
    if(pr[u] == u)return(u);
    return(pr[u] = fpr(pr[u]));
}
void unonl(int u, int v){
    v = fpl(v);
    if(u == v)return;
    
    pl[v] = u; adjl[u].pb(v);
}
void unonr(int u, int v){
    v = fpr(v);
    if(u == v)return;
    pr[v] = u; adjr[u].pb(v);
}
void dfsl(int s){
    
    if(s < n){
        tinl[s] = ++tt; tonodel[tt] = s;
    }
    else tinl[s] = 2 * n;
    for(auto i: adjl[s]){
    
        dfsl(i); tinl[s] = min(tinl[s], tinl[i]);
        
    }
    toutl[s] = tt;
}
void buildl(){
    for(int i = 0; i < n; i++)pl[i] = i;
    for(int i = n - 1; i >= 0; i--){
        int pos = n + i;
        pl[pos] = pos;
        unonl(pos, i);
        for(auto j: adj[i]){
            if(j > i){
                unonl(pos, j);
            }
        }
        for(auto [u, id]: ql[i]){
            int U = fpl(u); rootl[id] = U;
        }
    }
    pl[2 * n] = 2 * n;
    for(int i = 0; i <= n - 1; i++){
        
        unonl(2 * n, i);
    }
    dfsl(2 * n);
}
void dfsr(int s){
    
    if(s < n){
        
        tinr[s] = ++tt; tonoder[tt] = s;
    }
    else tinr[s] = 2 * n;
    for(auto i: adjr[s]){
        
            dfsr(i); tinr[s] = min(tinr[s], tinr[i]);
        
    }
    toutr[s] = tt;
}
void buildr(){
    for(int i = 0; i < n; i++)pr[i] = i;
    for(int i = 0; i < n; i++){
        int pos = n + i; pr[pos] = pos;
        unonr(pos, i);
        for(auto j: adjr[i]){
            if(j < i){
                unonr(pos, j);
            }
        }
        for(auto [u, id]: qr[i]){
            int U = fpr(u);
            rootr[id] = U;
        }
    }
    tt = 0; pr[2 * n] = 2 * n;
    for(int i = 0; i < n; i++){
        unonr(2 * n, i);
    }
    dfsr(2 * n);
}
struct Events{
    int type, y, l, r, id;
    bool operator <(const Events &b){
        if(y == b.y){
            return(type > b.type);
        }
        return(y < b.y);
    }
};
int bit[mxn + 1], before[mxn + 1], after[mxn + 1];
void upd(int p, int v){
    while(p <= mxn){
        bit[p] += v;
        p += p & (-p);
    }
}
int get(int p){
    int ans = 0;
    while(p){
        ans += bit[p];
        p -= p & (-p);
    }
    return(ans);
}
vt<Events>events;
vt<int>check_validity(int N, vt<int>x, vt<int>y, vt<int>s, vt<int>e, vt<int>l, vt<int>r){
    n = N;
    for(int i = 0; i < x.size(); i++){
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }
    for(int i = 0; i < l.size(); i++){
        ql[l[i]].pb(make_pair(s[i], i));
        qr[r[i]].pb(make_pair(e[i], i));
    }
    
    buildl(); 
    
    buildr();
    
    for(int i = 0; i < l.size(); i++){
       
        events.pb({1, tinr[rootr[i]], tinl[rootl[i]], toutl[rootl[i]], i});
        events.pb({-1, toutr[rootr[i]], tinl[rootl[i]], toutl[rootl[i]], i});
    }
    for(int i = 0; i < n; i++){
        events.pb({0, tinr[i], tinl[i], -1, -1});
    }
    sort(events.begin(), events.end());
    for(auto [type, y, l, r, id]: events){
        if(type == 0){
            upd(l, 1);
        }else if(type == 1){
            before[id] = get(r) - get(l - 1);
        }else{
            after[id] = get(r) - get(l - 1);
        }
    }
    
    vt<int>ans;
    for(int i = 0; i < l.size(); i++){
        ans.pb((bool)(before[i] < after[i]));
    }
    return(ans);
    

}

Compilation message (stderr)

werewolf.cpp: In function 'void buildl()':
werewolf.cpp:81:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |         for(auto [u, id]: ql[i]){
      |                  ^
werewolf.cpp: In function 'void buildr()':
werewolf.cpp:116:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |         for(auto [u, id]: qr[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:154:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for(int i = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:158:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int i = 0; i < l.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:167:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for(int i = 0; i < l.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:176:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  176 |     for(auto [type, y, l, r, id]: events){
      |              ^
werewolf.cpp:187:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for(int i = 0; i < l.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp: At global scope:
werewolf.cpp:21:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
   21 | int read_int() {
      |     ^~~~~~~~

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