oj.uz

Submission #835449

# Submission time Handle Problem Language Result Execution time Memory
835449 2023-08-23T14:36:49 Z mousebeaver Werewolf (IOI18_werewolf) C++14
49 / 100
 2142 ms 35664 KB 
#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][0];
        }
    }

    //build segtree:
    int segnodes = 1;
    while(2*n > segnodes)
    {
        segnodes *= 2;
    }
    vector<pii> s(segnodes, {INF, 0}); //min, max
    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 = 1;
            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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 232 ms 720 KB Output is correct
11 Correct 146 ms 600 KB Output is correct
12 Correct 29 ms 852 KB Output is correct
13 Correct 230 ms 768 KB Output is correct
14 Correct 175 ms 720 KB Output is correct
15 Correct 156 ms 800 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2081 ms 27168 KB Output is correct
2 Correct 2074 ms 27164 KB Output is correct
3 Correct 2142 ms 27168 KB Output is correct
4 Correct 2126 ms 27168 KB Output is correct
5 Correct 2021 ms 27160 KB Output is correct
6 Correct 1917 ms 27160 KB Output is correct
7 Correct 2051 ms 27160 KB Output is correct
8 Correct 2108 ms 27160 KB Output is correct
9 Correct 1380 ms 27148 KB Output is correct
10 Correct 1545 ms 27160 KB Output is correct
11 Correct 1776 ms 27164 KB Output is correct
12 Correct 1553 ms 27168 KB Output is correct
13 Correct 2128 ms 27160 KB Output is correct
14 Correct 2106 ms 27164 KB Output is correct
15 Correct 2067 ms 27160 KB Output is correct
16 Correct 2100 ms 27164 KB Output is correct
17 Correct 2019 ms 27160 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 232 ms 720 KB Output is correct
11 Correct 146 ms 600 KB Output is correct
12 Correct 29 ms 852 KB Output is correct
13 Correct 230 ms 768 KB Output is correct
14 Correct 175 ms 720 KB Output is correct
15 Correct 156 ms 800 KB Output is correct
16 Correct 2081 ms 27168 KB Output is correct
17 Correct 2074 ms 27164 KB Output is correct
18 Correct 2142 ms 27168 KB Output is correct
19 Correct 2126 ms 27168 KB Output is correct
20 Correct 2021 ms 27160 KB Output is correct
21 Correct 1917 ms 27160 KB Output is correct
22 Correct 2051 ms 27160 KB Output is correct
23 Correct 2108 ms 27160 KB Output is correct
24 Correct 1380 ms 27148 KB Output is correct
25 Correct 1545 ms 27160 KB Output is correct
26 Correct 1776 ms 27164 KB Output is correct
27 Correct 1553 ms 27168 KB Output is correct
28 Correct 2128 ms 27160 KB Output is correct
29 Correct 2106 ms 27164 KB Output is correct
30 Correct 2067 ms 27160 KB Output is correct
31 Correct 2100 ms 27164 KB Output is correct
32 Correct 2019 ms 27160 KB Output is correct
33 Incorrect 584 ms 35664 KB Output isn't correct
34 Halted 0 ms 0 KB -