oj.uz

Submission #1077915

# Submission time Handle Problem Language Result Execution time Memory
1077915 2024-08-27T10:29:37 Z asdasdqwer Werewolf (IOI18_werewolf) C++14
49 / 100
 293 ms 72440 KB 
#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

struct DMin {
    vector<int> p, r;

    DMin(int n, vector<int> &pr) : p(n) {
        for (int i=0;i<n;i++) {
            p[i]=i;
        }
        r=pr;
    }

    int get(int i) {
        if (i != p[i])p[i]=get(p[i]);
        return p[i];
    }

    void unite(int a, int b) {
        a=get(a);b=get(b);
        if (r[a] > r[b])swap(a,b);
        p[b]=a;
    }
};

struct DMax {
    vector<int> p, r;

    DMax(int n, vector<int> &pr) : p(n) {
        for (int i=0;i<n;i++) {
            p[i]=i;
        }
        r=pr;
    }

    int get(int i) {
        if (i != p[i])p[i]=get(p[i]);
        return p[i];
    }

    void unite(int a, int b) {
        a=get(a);b=get(b);
        if (r[a] < r[b])swap(a,b);
        p[b]=a;
    }
};


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) {
    vector<vector<int>> g(N);
    int M = X.size(), Q=S.size();
    for (int i=0;i<M;i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    vector<int> ans(Q,0);
    if (N <= 3000 && M <= 6000 && Q <= 3000) {
        for (int i=0;i<Q;i++) {
            vector<bool> vis1(N, false), vis2(N, false);
            function<void(int)> dfs1=[&](int node) {
                vis1[node]=true;
                for (auto &x:g[node]) {
                    if (x >= L[i] && !vis1[x]) dfs1(x);
                }
            };

            function<void(int)> dfs2=[&](int node) {
                vis2[node]=true;
                for (auto &x:g[node]) {
                    if (x <= R[i] && !vis2[x]) dfs2(x);
                }
            };

            dfs1(S[i]);dfs2(E[i]);
            for (int j=L[i];j<=R[i];j++) {
                if (vis1[j] && vis2[j]) {
                    ans[i]=true;break;
                }
            }
        }
        return ans;
    }

    // first find node with degree one
    int node = -1;
    for (int i=0;i<N;i++) {
        if (g[i].size() == 1) node = i;
    }

    vector<int> order(N, 0);
    function<void(int,int)> dfs=[&](int nd, int parent) {
        for (auto &x:g[nd]) {
            if (x == parent) continue;
            order[x] = order[nd]+1;
            dfs(x, nd);
        }
    };

    dfs(node, -1);

    DMin dmn(N, order);
    DMax dmx(N, order);

    vector<int> far(Q, -1);
    vector<vector<int>> newl(N), newr(N);
    for (int i=0;i<Q;i++) {
        newl[L[i]].push_back(i);
        newr[R[i]].push_back(i);
    }
    for (int i=N-1;i>=0;i--) {
        for (auto &x:g[i]) {
            if (x > i) {
                dmn.unite(x, i);
                dmx.unite(x, i);
            }
        }

        for (auto &x : newl[i]) {
            if (order[S[x]] < order[E[x]]) {
                far[x] = dmx.get(S[x]);
            }

            else {
                far[x] = dmn.get(S[x]);
            }
        }
    }

    DMin dmn2(N, order);
    DMax dmx2(N, order);
    for (int i=0;i<N;i++) {
        for (auto &x:g[i]) {
            if (x < i) {
                dmn2.unite(x, i);
                dmx2.unite(x, i);
            }
        }

        for (auto &x : newr[i]) {
            int far2;
            if (order[S[x]] < order[E[x]]) {
                far2 = dmn2.get(E[x]);
                if (order[far[x]] >= order[far2]) ans[x]=true;
            }

            else {
                far2 = dmx2.get(E[x]);
                if (order[far[x]] <= order[far2]) ans[x]=true;
            }
        }
    }

    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 176 ms 856 KB Output is correct
11 Correct 76 ms 604 KB Output is correct
12 Correct 15 ms 856 KB Output is correct
13 Correct 191 ms 860 KB Output is correct
14 Correct 90 ms 844 KB Output is correct
15 Correct 194 ms 1016 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 72072 KB Output is correct
2 Correct 247 ms 72188 KB Output is correct
3 Correct 234 ms 72072 KB Output is correct
4 Correct 293 ms 72276 KB Output is correct
5 Correct 237 ms 72272 KB Output is correct
6 Correct 262 ms 72348 KB Output is correct
7 Correct 216 ms 70268 KB Output is correct
8 Correct 233 ms 72200 KB Output is correct
9 Correct 214 ms 71152 KB Output is correct
10 Correct 276 ms 70996 KB Output is correct
11 Correct 246 ms 71036 KB Output is correct
12 Correct 279 ms 71760 KB Output is correct
13 Correct 244 ms 72064 KB Output is correct
14 Correct 235 ms 72440 KB Output is correct
15 Correct 289 ms 72184 KB Output is correct
16 Correct 273 ms 72120 KB Output is correct
17 Correct 250 ms 70016 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 176 ms 856 KB Output is correct
11 Correct 76 ms 604 KB Output is correct
12 Correct 15 ms 856 KB Output is correct
13 Correct 191 ms 860 KB Output is correct
14 Correct 90 ms 844 KB Output is correct
15 Correct 194 ms 1016 KB Output is correct
16 Correct 263 ms 72072 KB Output is correct
17 Correct 247 ms 72188 KB Output is correct
18 Correct 234 ms 72072 KB Output is correct
19 Correct 293 ms 72276 KB Output is correct
20 Correct 237 ms 72272 KB Output is correct
21 Correct 262 ms 72348 KB Output is correct
22 Correct 216 ms 70268 KB Output is correct
23 Correct 233 ms 72200 KB Output is correct
24 Correct 214 ms 71152 KB Output is correct
25 Correct 276 ms 70996 KB Output is correct
26 Correct 246 ms 71036 KB Output is correct
27 Correct 279 ms 71760 KB Output is correct
28 Correct 244 ms 72064 KB Output is correct
29 Correct 235 ms 72440 KB Output is correct
30 Correct 289 ms 72184 KB Output is correct
31 Correct 273 ms 72120 KB Output is correct
32 Correct 250 ms 70016 KB Output is correct
33 Incorrect 235 ms 53840 KB Output isn't correct
34 Halted 0 ms 0 KB -