Submission #835428

#	Time	Username	Problem	Language	Result	Execution time	Memory
835428		mousebeaver	Werewolf (IOI18_werewolf)	C++14	15 / 100	227 ms	53336 KiB

werewolf

#define pii pair<int, int>
#define INF numeric_limits<int>::max()/2
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

void dfsSub1(int l, int r, vector<vector<int>>& adjlist, int i, vector<bool>& visited)
{
    visited[i] = true;
    for(int j : adjlist[i])
    {
        if(!visited[j] && l <= j && j <= r)
        {
            dfsSub1(l, r, adjlist, j, visited);
        }
    }
}

int left(int i)
{
    return 2*i;
}

int right(int i)
{
    return 2*i+1;
}

pii query(int i, vector<pii>& s, int a, int b, int l, int r)
{
    if(l <= a && b <= r)
    {
        return s[i];
    }
    if(r < a || b < l)
    {
        return {INF, 0};
    }

    int mid = (a+b)/2;
    pii one = query(left(i), s, a, mid, l, r);
    pii two = query(right(i), s, mid+1, b, l, r);

    pii res;
    res.first = min(one.first, two.first);
    res.second = max(one.second, two.second);
    return res;
}

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) 
{
    int n = N;
    vector<vector<int>> adjlist(n, vector<int> (0));
    for(int i = 0; i < (int) X.size(); i++)
    {
        int a = X[i];
        int b = Y[i];
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }

    if(N <= 3000 && (int) X.size() <= 6000 && (int) S.size() <= 3000)
    {

        vector<int> output(S.size());
        for(int t = 0; t < (int) S.size(); t++)
        {
            int l = L[t];
            int r = R[t];
            int s = S[t];
            int e = E[t];

            vector<bool> visited(n, false);
            dfsSub1(l, numeric_limits<int>::max()/2, adjlist, s, visited);
            for(int i = 0; i < n; i++)
            {
                if(visited[i] && l <= i && i <= r)
                {
                    dfsSub1(0, r, adjlist, i, visited);
                }
            }
            output[t] = visited[e];
        }
        return output;
    }

    //Now, we have a line
    vector<int> pos(n); //Index on line
    vector<int> line(n); //Index of line position in node array
    int start = 0;
    while(adjlist[start].size() == 2)
    {
        start++;
    }

    int counter = 0;
    vector<bool> visited(n, false);
    while(true)
    {
        pos[start] = counter;
        line[counter] = start;
        visited[start] = true;
        if(adjlist[start].size() == 1 && counter != 0)
        {
            break;
        }

        counter++;
        if(visited[adjlist[start][0]])
        {
            start = adjlist[start][1];
        }
        else
        {
            start = adjlist[start][1];
        }
    }

    //build segtree:
    int segnodes = 1;
    vector<pii> s(segnodes, {INF, 0}); //min, max
    while(2*n < segnodes)
    {
        segnodes *= 2;
    }
    for(int i = 0; i < n; i++)
    {
        s[i+segnodes/2] = {line[i], line[i]};
    }
    for(int i = segnodes/2-1; i > 0; i--)
    {
        s[i].first = min(s[left(i)].first, s[right(i)].first);
        s[i].second = max(s[left(i)].second, s[right(i)].second);
    }

    //Answer queries:
    vector<int> res(S.size());
    for(int t = 0; t < (int) S.size(); t++)
    {
        int l = L[t];
        int r = R[t];
        int start = S[t];
        int e = E[t];
        start = pos[start]+1;
        e = pos[e]+1;

        if(start < e)
        {
            //Going to the right

            //How far can the human go?
            int left = start;
            int right = n;
            while(left < right)
            {
                int mid = (left+right+1)/2;
                if(query(1, s, 1, segnodes/2, start, mid).first >= l)
                {
                    left = mid;
                }
                else
                {
                    right = mid-1;
                }
            }
            int human = left;

            //How far can the wolf go?
            left = 1;
            right = e;
            while(left < right)
            {
                int mid = (left+right)/2;
                if(query(1, s, 1, segnodes/2, mid, e).second <= r)
                {
                    right = mid;
                }
                else
                {
                    left = mid+1;
                }
            }
            int wolf = left;

            //Result:
            if(human >= wolf)
            {
                res[t] = 1;
            }
            else
            {
                res[t] = 0;
            }
        }
        else
        {
            //Going to the left

            //How far can the human go?
            int left = n;
            int right = start;
            while(left < right)
            {
                int mid = (left+right)/2;
                if(query(1, s, 1, segnodes/2, mid, start).first >= l)
                {
                    right = mid;
                }
                else
                {
                    left = mid+1;
                }
            }
            int human = left;

            //How far can the wolf go?
            left = e;
            right = n;
            while(left < right)
            {
                int mid = (left+right+1)/2;
                if(query(1, s, 1, segnodes/2, e, mid).second <= r)
                {
                    left = mid;
                }
                else
                {
                    right = mid-1;
                }
            }
            int wolf = left;

            //Result:
            if(human <= wolf)
            {
                res[t] = 1;
            }
            else
            {
                res[t] = 0;
            }
        }
    }
    return res;
}

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