oj.uz

Submission #582796

# Submission time Handle Problem Language Result Execution time Memory
582796 2022-06-24T12:39:48 Z PiejanVDC Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 98984 KB 
#include <bits/stdc++.h>
#include "werewolf.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) {

    vector<int>ri(n),li(n);
    vector<int>adj[n];
    vector<int>pos(n);

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

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

    int p = 0;

    vector<bool>vis(n,0);

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

    int rem = start;

    vis.clear();
    vis.resize(n,0);

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

    int q = (int)l.size();
    int jump[n+5][32];
    int mx[n+5][32];
    int mn[n+5][32];
    for(int i = 0 ; i < n ; i++) {
        jump[i][0] = ri[i];
        mx[i][0] = max(i, ri[i]);
        mn[i][0] = min(i, ri[i]);
    }
    jump[rem][0] = n;
    mx[rem][0] = max(rem, n);
    mn[rem][0] = min(rem, n);
    for(int j = 1 ; j <= 30 ; j++) {
        for(int i = 0 ; i < n ; i++) {
            jump[i][j] = jump[jump[i][j-1]][j-1];
            mx[i][j] = max(mx[i][j-1], mx[jump[i][j-1]][j-1]);
            mn[i][j] = min(mn[i][j-1], mn[jump[i][j-1]][j-1]);
        }
    }

    vector<int>ans(q,0);

    for(int i = 0 ; i < q ; i++) {
        if(pos[s[i]] < pos[e[i]]) {
            if(s[i] > r[i] || e[i] < l[i])
                continue;
        } else {
            if(s[i] > r[i] || e[i] < l[i])
                continue;
            swap(s[i],e[i]);
        }
            while(s[i] != e[i]) {
                bool f = 0;
                for(int j = 30 ; j >= 0 ; j--) {
                    if(pos[s[i]] + (1 << j) <= pos[e[i]] && !(mx[s[i]][j] - mn[s[i]][j] > r[i] - l[i] && mx[s[i]][j] > r[i] && mn[s[i]][j] < l[i]))
                        s[i] = jump[s[i]][j], f = 1;
                }
                if(!f)
                    break;
            }
            if(s[i] == e[i]) {
                ans[i] = 1;
            }
    }
    return ans;
}

Compilation message

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:17:9: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     int start;
      |         ^~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4069 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4069 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 1061 ms 98984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4069 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -