Submission #591094

#	Time	Username	Problem	Language	Result	Execution time	Memory
591094		PiejanVDC	Werewolf (IOI18_werewolf)	C++17	0 / 100	583 ms	124836 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

vector<int>check_validity(int n, vector<int>x, vector<int>y, vector<int>s, vector<int>e, vector<int>l, vector<int>r) {
    const int m = (int)x.size();
    const int q = (int)s.size();

    vector<int>ans(q, 0);

    int start;

    vector<int>adj[n];

    for(int i = 0 ; i < m ; i++) {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }

    for(int i = 0 ; i < n ; i++) {
        if(adj[i].size() == 1)
            start = i;
    }

    vector<int>v(n+1);
    vector<bool>vis(n, 0);

    vector<int>rev(n);

    for(int i = 0 ; i < n ; i++) {
        v[i] = start;
        vis[start] = 1;
        rev[start] = i;
        
        for(auto z : adj[start]) if(!vis[z]) start = z;
    }

    v[n] = n+5;

    int mx[n+1][32];
    int mn[n+1][32];

    int lmx[n+1][32];
    int lmn[n+1][32];

    for(int i = 0 ; i < n ; i++) {
        mn[i][0] = min(v[i], v[i+1]);
        mx[i][0] = max(v[i], v[max(0,i-1)]);
    }

    for(int j = 1 ; j <= 30 ; j++) {
        for(int i = 0 ; i <= n ; i++) {
            mx[i][j] = max(mx[i][j-1], mx[ max(0, i - (1 << j)) ][j-1]);
            mn[i][j] = min(mn[i][j-1], mn[ min(n, i + (1 << j)) ][j-1]);
        }
    }

    for(int i = 0 ; i < n ; i++) {
        lmx[i][0] = max(v[i], v[i+1]);
        lmn[i][0] = min(v[i], v[max(0,i-1)]);
    }

    for(int j = 1 ; j <= 30 ; j++) {
        for(int i = 0 ; i <= n ; i++) {
            lmx[i][j] = max(lmx[i][j-1], lmx[ min(n, i + (1 << j)) ][j-1]);
            lmn[i][j] = min(lmn[i][j-1], lmn[ max(0, i - (1 << j)) ][j-1]);
        }
    }

    for(int i = 0 ; i < q ; i++) {
        if(s[i] < l[i] || e[i] > r[i])
            continue;
        if(rev[s[i]] <= rev[e[i]]) {
            int x = rev[s[i]];
            
            for(int j = 30 ; j >= 0 ; j--) {
                if(mn[x][j] >= l[i])
                    x = min(n, x + (1 << j));
            }
            
            int y = rev[e[i]];
            
            for(int j = 30 ; j >= 0 ; j--) {
                if(mx[y][j] <= r[i])
                    y = max(0, y - (1 << j));
            }
            
            if(x >= y)
                ans[i] = 1; 
       
        } else {
            int x = rev[s[i]];
            
            for(int j = 30 ; j >= 0 ; j--) {
                if(lmn[x][j] >= l[i])
                    x = max(0, x - (1 << j));
            }
            
            int y = rev[e[i]];
            
            for(int j = 30 ; j >= 0 ; j--) {
                if(lmx[y][j] <= r[i])
                    y = min(n, y + (1 << j));
            }
            
            if(y >= x)
                ans[i] = 1; 
        }
    }
    return ans;
}

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