oj.uz

Submission #524606

# Submission time Handle Problem Language Result Execution time Memory
524606 2022-02-09T15:54:34 Z TITANOBOXER Werewolf (IOI18_werewolf) C++17
49 / 100
 3248 ms 292488 KB 
#include "werewolf.h"
#include <vector>
#include <set>
#include <iostream>

using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//#define int long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

const int SZ = 3e3 + 7;
const int R = 2e5 + 7;
const int LOG = 19;

vector<int> g[R];
int ver[R],pos[R];
int timer = 0;
vector<vector<int>> sp(R,vector<int> (LOG,2e9));
vector<vector<int>> sg(R,vector<int> (LOG,-2e9));
int mn[SZ][SZ];
int mx[SZ][SZ];

void dfs(int v,int p) {
    ver[timer] = v;
    pos[v] = timer;
    timer += 1;
    for(int u : g[v]) {
        if(u == p) continue;
        dfs(u,v);
    }
}

int get_min(int l,int r) {
    int k = __lg(r - l + 1);
    return min(sp[l][k],sp[r - (1 << k) + 1][k]);
}

int get_max(int l,int r) {
    int k = __lg(r - l + 1);
    return max(sg[l][k],sg[r - (1 << k) + 1][k]);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
    int M = X.size(),Q = L.size();
    for(int i = 0; i < M; ++i) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    bool ok = (N - 1 == M);
    int cnt = 0;
    for(int i = 0; i < N; ++i) {
        if(g[i].size() == 1) {
            cnt += 1;
        }
    }
    ok &= (cnt == 2);
    if(!ok) {
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                mn[i][j] = 2e9;
                mx[i][j] = -2e9;
            }
        }
        set<pair<int,int>> st;
        for(int i = 0; i < N; ++i) {
            st.insert({0,i});
            mn[i][i] = i;
            while(st.size()) {
                pair<int,int> p = *st.begin();
                int v = p.ss;
                st.erase(st.begin());
                for(int u : g[v]) {
                    if(mn[i][u] > max(mn[i][v],u)) {
                        st.erase({mn[i][u],u});
                        mn[i][u] = max(mn[i][v],u);
                        st.insert({mn[i][u],u});
                    }
                }
            }
            st.insert({i,i});
            mx[i][i] = i;
            while(st.size()) {
                pair<int,int> p = *(--st.end());
                int v = p.ss;
                st.erase(--st.end());
                for(int u : g[v]) {
                    if(mx[i][u] < min(mx[i][v],u)) {
                        st.erase({mn[i][u],u});
                        mx[i][u] = min(mx[i][v],u);
                        st.insert({mx[i][u],u});
                    }
                }
            }
        }
        vector<int> ans(Q);
        for(int i = 0; i < Q; ++i) {
            int s = S[i],e = E[i];
            for(int v = 0; v < N; ++v) {
                if(mx[s][v] >= L[i] && mn[v][e] <= R[i]) {
                    ans[i] = 1;
                    break;
                }
            }
        }
        return ans;
    }
    int kor = 0;
    for(int i = 0; i < N; ++i) {
        if(g[i].size() == 1) {
            kor = i;
            break;
        }
    }
    dfs(kor,-1);
    for(int i = 0; i < timer; ++i) {
        sp[i][0] = ver[i];
        sg[i][0] = ver[i];
    }
    for(int log = 1; log < LOG; ++log) {
        for(int i = 0; i + (1 << (log - 1)) < timer; ++i) {
            sp[i][log] = min(sp[i][log - 1],sp[i + (1 << (log - 1))][log - 1]);
            sg[i][log] = max(sg[i][log - 1],sg[i + (1 << (log - 1))][log - 1]);
        }
    }
    vector<int> ans(Q);
    for(int i = 0; i < Q; ++i) {
        int s = S[i],e = E[i];
        if(pos[s] <= pos[e]) {
            int v = pos[s];
            for(int log = LOG - 1; log >= 0; --log) {
                if(log != 0) {
                    while(v + (1 << log) - 1 <= pos[e] && sp[v][log] >= L[i]) {
                        v = v + (1 << log) - 1;
                    }
                } else {
                    if(v + (1 << log) - 1 <= pos[e] && sp[v][log] >= L[i]) {
                        v = v + (1 << log) - 1;
                    }
                }
            }
            if(get_max(v,pos[e]) <= R[i]) {
                ans[i] = 1;
            }
        } else {
            int v = pos[e];
            for(int log = LOG - 1; log >= 0; --log) {
                if(log != 0) {
                    while(v + (1 << log) - 1 <= pos[s] && sg[v][log] <= R[i]) {
                        v = v + (1 << log) - 1;
                    }
                } else {
                    if(v + (1 << log) - 1 <= pos[s] && sg[v][log] <= R[i]) {
                        v = v + (1 << log) - 1;
                    }
                }
            }
            if(get_min(v,pos[s]) >= L[i]) {
                ans[i] = 1;
            }
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 52804 KB Output is correct
2 Correct 45 ms 52868 KB Output is correct
3 Correct 38 ms 52184 KB Output is correct
4 Correct 36 ms 51908 KB Output is correct
5 Correct 41 ms 52764 KB Output is correct
6 Correct 41 ms 52856 KB Output is correct
7 Correct 42 ms 52768 KB Output is correct
8 Correct 36 ms 51912 KB Output is correct
9 Correct 41 ms 52800 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 52804 KB Output is correct
2 Correct 45 ms 52868 KB Output is correct
3 Correct 38 ms 52184 KB Output is correct
4 Correct 36 ms 51908 KB Output is correct
5 Correct 41 ms 52764 KB Output is correct
6 Correct 41 ms 52856 KB Output is correct
7 Correct 42 ms 52768 KB Output is correct
8 Correct 36 ms 51912 KB Output is correct
9 Correct 41 ms 52800 KB Output is correct
10 Correct 2719 ms 122956 KB Output is correct
11 Correct 2567 ms 122940 KB Output is correct
12 Correct 39 ms 52420 KB Output is correct
13 Correct 2953 ms 122992 KB Output is correct
14 Correct 2706 ms 122980 KB Output is correct
15 Correct 3248 ms 123112 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 87796 KB Output is correct
2 Correct 448 ms 87812 KB Output is correct
3 Correct 465 ms 87920 KB Output is correct
4 Correct 524 ms 87812 KB Output is correct
5 Correct 512 ms 87736 KB Output is correct
6 Correct 423 ms 87900 KB Output is correct
7 Correct 430 ms 87884 KB Output is correct
8 Correct 395 ms 87772 KB Output is correct
9 Correct 333 ms 87788 KB Output is correct
10 Correct 336 ms 87796 KB Output is correct
11 Correct 342 ms 87896 KB Output is correct
12 Correct 342 ms 87892 KB Output is correct
13 Correct 465 ms 87828 KB Output is correct
14 Correct 472 ms 87936 KB Output is correct
15 Correct 448 ms 87880 KB Output is correct
16 Correct 427 ms 87748 KB Output is correct
17 Correct 419 ms 87748 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 52804 KB Output is correct
2 Correct 45 ms 52868 KB Output is correct
3 Correct 38 ms 52184 KB Output is correct
4 Correct 36 ms 51908 KB Output is correct
5 Correct 41 ms 52764 KB Output is correct
6 Correct 41 ms 52856 KB Output is correct
7 Correct 42 ms 52768 KB Output is correct
8 Correct 36 ms 51912 KB Output is correct
9 Correct 41 ms 52800 KB Output is correct
10 Correct 2719 ms 122956 KB Output is correct
11 Correct 2567 ms 122940 KB Output is correct
12 Correct 39 ms 52420 KB Output is correct
13 Correct 2953 ms 122992 KB Output is correct
14 Correct 2706 ms 122980 KB Output is correct
15 Correct 3248 ms 123112 KB Output is correct
16 Correct 425 ms 87796 KB Output is correct
17 Correct 448 ms 87812 KB Output is correct
18 Correct 465 ms 87920 KB Output is correct
19 Correct 524 ms 87812 KB Output is correct
20 Correct 512 ms 87736 KB Output is correct
21 Correct 423 ms 87900 KB Output is correct
22 Correct 430 ms 87884 KB Output is correct
23 Correct 395 ms 87772 KB Output is correct
24 Correct 333 ms 87788 KB Output is correct
25 Correct 336 ms 87796 KB Output is correct
26 Correct 342 ms 87896 KB Output is correct
27 Correct 342 ms 87892 KB Output is correct
28 Correct 465 ms 87828 KB Output is correct
29 Correct 472 ms 87936 KB Output is correct
30 Correct 448 ms 87880 KB Output is correct
31 Correct 427 ms 87748 KB Output is correct
32 Correct 419 ms 87748 KB Output is correct
33 Runtime error 802 ms 292488 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -