Submission #1024211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024211		ksu2009en	Werewolf (IOI18_werewolf)	C++17	0 / 100	814 ms	40648 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef int ll;

vector<ll> d[200007];

bool used1[200007], used2[200007];

ll lim = 0;

void dfs1(ll v){
    if(v < lim)
        return;
    
    used1[v] = true;
    for(auto i: d[v]){
        if(!used1[i] && i >= lim)
            dfs1(i);
    }
}

void dfs2(ll v){
    if(v > lim)
        return;
    
    used2[v] = true;
    for(auto i: d[v]){
        if(!used2[i] && i <= lim)
            dfs2(i);
    }
}

vector<ll> ord;

void dfs(ll v, ll par){
    ord.push_back(v);
    
    for(auto i: d[v])
        if(i != par)
            dfs(i, v);
}

ll a[200007];

pair<ll, ll> t[800007];

void build(ll v, ll l, ll r){
    if(l == r){
        t[v] = {a[l], a[l]};
        return;
    }
    
    ll mid = (l + r) >> 1;
    build(2 * v, l, mid);
    build(2 * v + 1, mid + 1, r);
    
    t[v].first = min(t[2 * v].first, t[2 * v + 1].first);
    t[v].second = max(t[2 * v].second, t[2 * v + 1].second);
}

ll get(ll v, ll l, ll r, ll ql, ll qr, bool mn){
    if(r < ql || qr < l)
        return (mn ? (ll)(1e9) : (ll)(-1e9));
    
    if(ql <= l && r <= qr)
        return (mn ? t[v].first : t[v].second);
    
    ll mid = (l + r) >> 1;
    if(mn)
        return min(get(2 * v, l, mid, ql, qr, mn), get(2 * v + 1, mid + 1, r, ql, qr, mn));
    
    return max(get(2 * v, l, mid, ql, qr, mn), get(2 * v + 1, mid + 1, r, ql, qr, mn));
}

std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,
                                std::vector<int> s, std::vector<int> e,
                                std::vector<int> l, std::vector<int> r) {
    
    ll q = l.size();
    
    for(int i = 0; i < x.size(); i++){
        d[x[i]].push_back(y[i]);
        d[y[i]].push_back(x[i]);
    }
    
    vector<int> ans;
    
    if(x.size() == n - 1){
        for(int i = 0; i < n; i++){
            if(d[i].size() == 1){
                dfs(i, -1);
                break;
            }
        }
        
        vector<ll> pos(n + 1);
        for(int i = 0; i < n; i++){
            a[i + 1] = ord[i] + 1;
            
            pos[a[i + 1]] = i + 1;
        }
        
        for(int i = 0; i < q; i++)
            s[i]++, e[i]++, l[i]++, r[i]++;
        
        build(1, 1, n);
        
        for(int i = 0; i < q; i++){
            ll a = pos[s[i]], b = pos[e[i]];
            ll p1 = 0, p2 = 0;
            
            ll l0 = a, r0 = b;
            while(l0 < r0){
                ll mid = (l0 + r0 + 1) >> 1;
                
                if(get(1, 1, n, a, mid, true) < l[i])
                    r0 = mid - 1;
                else
                    l0 = mid;
            }
            
            p1 = l0;
            
            l0 = a, r0 = b;
            while(l0 < r0){
                ll mid = (l0 + r0) >> 1;
                
                if(get(1, 1, n, a, mid, false) > r[i])
                    l0 = mid + 1;
                else
                    r0 = mid;
            }
            
            p2 = l0;
            
            if(p1 >= p2)
                ans.push_back(1);
            else
                ans.push_back(0);
        }
        
        return ans;
    }
    
    for(int i = 0; i < q; i++){
        lim = l[i];
        
        dfs1(s[i]);
        lim = r[i];
        dfs2(e[i]);
        
        int res = 0;
        for(int j = 0; j < n; j++){
            if(used1[j] && used2[j]){
                res = 1;
            }
            
            used1[j] = used2[j] = 0;
        }
        
        ans.push_back(res);
    }
    
    return ans;
}
/*
 6 6 3
 0 3
 3 1
 3 4
 1 2
 2 5
 1 5
 4 2 1 2
 4 2 2 2
 5 4 3 4
 
 */

/*
 6 6 1
 0 3
 3 1
 3 4
 1 2
 2 5
 1 5
 4 2 1 2
 
 4 2 2 2
 5 4 3 4
 */

/*
 4 3 1
 3 1
 0 2
 1 0
 3 2 1 2
 
 */

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:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:106:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     if(x.size() == n - 1){
      |        ~~~~~~~~~^~~~~~~~

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