oj.uz

Submission #759407

# Submission time Handle Problem Language Result Execution time Memory
759407 2023-06-16T09:17:01 Z yellowtoad Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 166004 KB 
#include "werewolf.h"
#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;
 
int n, m, q, p[200010], id[200010], pmax[600010][21], pmin[600010][21], vmax[600010], vmin[600010], mxsz, mnsz, cnt;
pair<int,int> rmax[600010], rmin[600010];
vector<int> edge[200010], maxx[600010], minn[600010], node[800010];
 
int dsu(int u) {
    if (p[u] == u) return u;
    return (p[u] = dsu(p[u]));
}
 
void buildmax(int u) {
    int v = pmax[u][0];
    for (int i = 1; i <= 20; i++) {
        if (v == -1) break;
        pmax[u][i] = pmax[v][i-1];
        v = pmax[u][i];
    }
    if (maxx[u].empty()) {
        ++cnt;
        rmax[u] = {cnt,cnt};
        return;
    }
    for (int i = 0; i < maxx[u].size(); i++) {
        buildmax(maxx[u][i]);
        rmax[u] = {min(rmax[u].f,rmax[maxx[u][i]].f),max(rmax[u].s,rmax[maxx[u][i]].s)};
    }
}
 
void buildmin(int u) {
    int v = pmin[u][0];
    for (int i = 1; i <= 20; i++) {
        if (v == -1) break;
        pmin[u][i] = pmin[v][i-1];
        v = pmin[u][i];
    }
    if (minn[u].empty()) {
        node[1].push_back(rmax[u].f);
        rmin[u] = {cnt,cnt};
        cnt++;
        return;
    }
    for (int i = 0; i < minn[u].size(); i++) {
        buildmin(minn[u][i]);
        rmin[u] = {min(rmin[u].f,rmin[minn[u][i]].f),max(rmin[u].s,rmin[minn[u][i]].s)};
    }
}
 
std::vector<signed> check_validity(signed N, std::vector<signed> X, std::vector<signed> Y, std::vector<signed> S, std::vector<signed> E, std::vector<signed> L, std::vector<signed> R) {
    vector<int> ans;
    n = N; m = X.size(); q = S.size();
    for (int i = 0; i < m; i++) {
        edge[X[i]].push_back(Y[i]);
        edge[Y[i]].push_back(X[i]);
    }
    for (int i = 0; i < n+m; i++) for (int j = 0; j <= 20; j++) pmax[i][j] = pmin[i][j] = -1;
    for (int i = 0; i < n; i++) p[i] = id[i] = vmin[i] = i;
    mnsz = n-1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < edge[i].size(); j++) {
            if (edge[i][j] < i) {
                int u = edge[i][j], v = i;
                if (p[dsu(u)] != p[dsu(v)]) {
                    ++mnsz;
                    pmin[id[p[dsu(u)]]][0] = pmin[id[p[dsu(v)]]][0] = mnsz;
                    minn[mnsz].push_back(id[p[dsu(u)]]);
                    minn[mnsz].push_back(id[p[dsu(v)]]);
                    p[dsu(v)] = p[dsu(u)];
                    id[p[dsu(u)]] = mnsz;
                    vmin[mnsz] = i;
                }
            }
        }
    }
    mxsz = n-1;
    for (int i = 0; i < n; i++) p[i] = id[i] = vmax[i] = i;
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < edge[i].size(); j++) {
            if (edge[i][j] > i) {
                int u = edge[i][j], v = i;
                if (p[dsu(u)] != p[dsu(v)]) {
                    ++mxsz;
                    pmax[id[p[dsu(u)]]][0] = pmax[id[p[dsu(v)]]][0] = mxsz;
                    maxx[mxsz].push_back(id[p[dsu(u)]]);
                    maxx[mxsz].push_back(id[p[dsu(v)]]);
                    p[dsu(v)] = p[dsu(u)];
                    id[p[dsu(u)]] = mxsz;
                    vmax[mxsz] = i;
                }
            }
        }
    }
    for (int i = 0; i <= mxsz; i++) rmax[i] = {1e9,-1e9};
    for (int i = 0; i <= mnsz; i++) rmin[i] = {1e9,-1e9};
    buildmax(mxsz);
    cnt = 0;
    buildmin(mnsz);
    for (int _ = 0; _ < q; _++) {
        int u = S[_], v = E[_], l = L[_], r = R[_];
        for (int j = 20; j >= 0; j--) if ((pmax[u][j] != -1) && (vmax[pmax[u][j]] >= l)) u = pmax[u][j];
        for (int j = 20; j >= 0; j--) if ((pmin[v][j] != -1) && (vmin[pmin[v][j]] <= r)) v = pmin[v][j];
        for (int i = rmin[v].f; i <= rmin[v].s; i++) {
            if ((rmax[u].f <= node[1][i]) && (node[1][i] <= rmax[u].s)) {
                ans.push_back(1);
                goto skip;
            }
        }
        ans.push_back(0);
        skip:;
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'void buildmax(int)':
werewolf.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < maxx[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void buildmin(int)':
werewolf.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < minn[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
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:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int j = 0; j < edge[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
werewolf.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int j = 0; j < edge[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 51956 KB Output is correct
2 Correct 24 ms 52068 KB Output is correct
3 Correct 23 ms 52044 KB Output is correct
4 Correct 32 ms 51952 KB Output is correct
5 Correct 25 ms 51976 KB Output is correct
6 Correct 25 ms 52004 KB Output is correct
7 Correct 27 ms 51972 KB Output is correct
8 Correct 25 ms 51976 KB Output is correct
9 Correct 28 ms 52088 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 51956 KB Output is correct
2 Correct 24 ms 52068 KB Output is correct
3 Correct 23 ms 52044 KB Output is correct
4 Correct 32 ms 51952 KB Output is correct
5 Correct 25 ms 51976 KB Output is correct
6 Correct 25 ms 52004 KB Output is correct
7 Correct 27 ms 51972 KB Output is correct
8 Correct 25 ms 51976 KB Output is correct
9 Correct 28 ms 52088 KB Output is correct
10 Correct 30 ms 53844 KB Output is correct
11 Correct 31 ms 53708 KB Output is correct
12 Correct 34 ms 53688 KB Output is correct
13 Correct 40 ms 53932 KB Output is correct
14 Correct 36 ms 53764 KB Output is correct
15 Correct 30 ms 54356 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 159184 KB Output is correct
2 Correct 626 ms 166004 KB Output is correct
3 Correct 678 ms 162780 KB Output is correct
4 Correct 3985 ms 161680 KB Output is correct
5 Execution timed out 4096 ms 161432 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 51956 KB Output is correct
2 Correct 24 ms 52068 KB Output is correct
3 Correct 23 ms 52044 KB Output is correct
4 Correct 32 ms 51952 KB Output is correct
5 Correct 25 ms 51976 KB Output is correct
6 Correct 25 ms 52004 KB Output is correct
7 Correct 27 ms 51972 KB Output is correct
8 Correct 25 ms 51976 KB Output is correct
9 Correct 28 ms 52088 KB Output is correct
10 Correct 30 ms 53844 KB Output is correct
11 Correct 31 ms 53708 KB Output is correct
12 Correct 34 ms 53688 KB Output is correct
13 Correct 40 ms 53932 KB Output is correct
14 Correct 36 ms 53764 KB Output is correct
15 Correct 30 ms 54356 KB Output is correct
16 Correct 591 ms 159184 KB Output is correct
17 Correct 626 ms 166004 KB Output is correct
18 Correct 678 ms 162780 KB Output is correct
19 Correct 3985 ms 161680 KB Output is correct
20 Execution timed out 4096 ms 161432 KB Time limit exceeded
21 Halted 0 ms 0 KB -