oj.uz

Submission #1044611

# Submission time Handle Problem Language Result Execution time Memory
1044611 2024-08-05T11:37:37 Z VMaksimoski008 Werewolf (IOI18_werewolf) C++17
0 / 100
 253 ms 80980 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 6e5 + 5;
vector<int> graph[maxn];
int vis[maxn][2], val[maxn], timer = 1, pos[maxn], log_dp[maxn];
pair<int, int> T[maxn+5][21];

void dfs(int u, int p) {
    pos[u] = timer; val[timer++] = u;
    for(int &v : graph[u]) if(v != p) dfs(v, u);
}

pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
    return { min(a.first, b.first), max(a.second, b.second) };
}

pair<int, int> query(int l, int r) {
    int k = log_dp[r-l+1];
    return merge(T[l][k], T[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 Q = S.size(), M = X.size();
    vector<int> ans(Q);

    for(int i=0; i<M; i++) {
        X[i]++; Y[i]++;
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    if(M == N - 1) {
        for(int i=1; i<=N; i++) {
            if(graph[i].size() == 1) {
                dfs(i, i);
                break;
            }
        }

        for(int i=2; i<=N; i++) log_dp[i] = log_dp[i/2] + 1;
        for(int i=1; i<=N; i++) T[i][0] = { val[i], val[i] };

        for(int j=1; j<21; j++)
            for(int i=1; i+(1<<j)-1<=N; i++) T[i][j] = merge(T[i][j-1], T[i+(1<<(j-1))][j-1]);

        for(int i=0; i<Q; i++) {
            S[i]++; E[i]++; L[i]++; R[i]++;
            if(S[i] < L[i] || E[i] > R[i]) continue;

            vector<pair<int, int> > vec = { { pos[S[i]], 0 }, { pos[E[i]], 1 } };
            sort(vec.begin(), vec.end());

            vector<int> P = { vec[0].first, vec[1].first };

            for(int j=0; j<2; j++) {
                int l, r;
                if(vec[j].second == 0) l = vec[j].first, r = N;
                else l = 1, r = vec[j].first;

                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(vec[j].second == 0) {
                        if(query(vec[j].first, mid).first >= L[i]) P[j] = mid, l = mid + 1;
                        else r = mid - 1;
                    } else {    
                        if(query(mid, vec[j].first).second <= R[i]) P[j] = mid, r = mid - 1;
                        else l = mid + 1;
                    }
                }
            }

            if(P[0] >= P[1]) ans[i] = 1;
        }

        return ans;
    }

    for(int i=0; i<Q; i++) {
        S[i]++; E[i]++; L[i]++; R[i]++;
        queue<pair<int, int> > q;
        memset(vis, 0, sizeof(vis));
        q.push({ S[i], 0 });
        vis[S[i]][0] = 1;

        while(!q.empty()) {
            auto [u, t] = q.front(); q.pop();

            if(t == 0) {
                if(u >= L[i] && u <= R[i] && !vis[u][1]) {
                    vis[u][1] = 1;
                    q.push({ u, 1 });
                }
            }

            for(int &v : graph[u]) {
                if(vis[v][t]) continue;
                if(t == 0 && v < L[i]) continue;
                if(t == 1 && v > R[i]) continue;
                vis[v][t] = 1; q.push({ v, t });
            }
        }

        ans[i] = vis[E[i]][1];
    }

    return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20056 KB Output is correct
2 Incorrect 3 ms 20060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20056 KB Output is correct
2 Incorrect 3 ms 20060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20056 KB Output is correct
2 Incorrect 3 ms 20060 KB Output isn't correct
3 Halted 0 ms 0 KB -