oj.uz

Submission #370873

# Submission time Handle Problem Language Result Execution time Memory
370873 2021-02-24T20:59:07 Z thecodingwizard Werewolf (IOI18_werewolf) C++11
7 / 100
 4000 ms 41272 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

#define pi pair<int, int>
#define f first
#define s second
#define mp make_pair

vector<int> adj[200000];
int id[200000];
int idRev[200000];
int id2[200000];
int id2Rev[200000];
bool vis[200000];
pi rangeL[200000];
pi rangeR[200000];
int pa[200000];
int sz[200000];
pi range[200000];

int get(int x) {
    return pa[x] == x ? x : pa[x] = get(pa[x]);
}
void unite(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    pa[a] = b;
    sz[b] += sz[a];
    range[b].f = min(range[b].f, range[a].f);
    range[b].s = max(range[b].s, range[a].s);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    for (int i = 0; i < (int)X.size(); i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    int ctr = 0;
    priority_queue<int, vector<int>, greater<int>> q;
    q.push(0); vis[0] = true;
    while (!q.empty()) {
        int u = q.top(); q.pop();
        idRev[ctr] = u;
        id[u] = ctr++;
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    for (int i = 0; i < N; i++) vis[i] = 0;
    ctr = 0;
    priority_queue<int> q2;
    q2.push(N-1); vis[N-1] = true;
    while (!q2.empty()) {
        int u = q2.top(); q2.pop();
        id2Rev[ctr] = u;
        id2[u] = ctr++;
        //cout << u << " is " << ctr-1 << endl;
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q2.push(v);
            }
        }
    }

    vector<int> queries;
    for (int i = 0; i < S.size(); i++) {
        queries.push_back(i);
    }

    int qryIdx = 0;
    sort(queries.begin(), queries.end(), [&R](int a, int b) {
        return R[a] < R[b];
    });
    for (int i = 0; i < N; i++) range[i] = mp(id[i], id[i]), pa[i] = i, sz[i] = 1;
    for (int i = 0; i < N; i++) {
        for (int v : adj[i]) {
            if (v < i) unite(i, v);
        }
        while (qryIdx < S.size() && R[queries[qryIdx]] <= i) {
            rangeR[queries[qryIdx]] = range[get(E[queries[qryIdx]])];
            qryIdx++;
        }
    }
    qryIdx = 0;
    sort(queries.begin(), queries.end(), [&L](int a, int b) {
        return L[a] > L[b];
    });
    for (int i = 0; i < N; i++) range[i] = mp(id2[i], id2[i]), pa[i] = i, sz[i] = 1;
    for (int i = N-1; ~i; i--) {
        for (int v : adj[i]) {
            if (v > i) unite(i, v);
        }
        while (qryIdx < S.size() && L[queries[qryIdx]] >= i) {
            rangeL[queries[qryIdx]] = range[get(S[queries[qryIdx]])];
            qryIdx++;
        }
    }

    int Q = S.size();
    vector<int> A(Q);
    for (int i = 0; i < Q; ++i) {
        pi lrange = rangeL[i], rrange = rangeR[i];
        //cout << i << ": (" << lrange.f << "," << lrange.s << ") -- (" << rrange.f << "," << rrange.s << ")\n";
        A[i] = 0;
        set<int> lft2;
        for (int j = lrange.f; j <= lrange.s; j++) {
            assert(id2Rev[j] >= L[i]);
            lft2.insert(id2Rev[j]);
        }
        for (int j = rrange.f; j <= rrange.s; j++) {
            assert(idRev[j] <= R[i]);
            if (lft2.count(idRev[j])) A[i] = 1;
        }
        assert(E[i] <= R[i]);
        assert(S[i] >= L[i]);
        A[i] = 0;
        queue<int> q;
        set<int> lft;
        set<int> rht;
        q.push(S[i]); lft.insert(S[i]);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (v >= L[i] && !lft.count(v)) {
                    lft.insert(v);
                    q.push(v);
                }
            }
        }
        assert(lft2.size() >= lft.size());
        q.push(E[i]); rht.insert(E[i]);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (lft.count(u)) A[i] = 1;
            for (int v : adj[u]) {
                if (v <= R[i] && !rht.count(v)) {
                    rht.insert(v);
                    q.push(v);
                }
            }
        }
    }
    return A;
}

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:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < S.size(); i++) {
      |                     ~~^~~~~~~~~~
werewolf.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         while (qryIdx < S.size() && R[queries[qryIdx]] <= i) {
      |                ~~~~~~~^~~~~~~~~~
werewolf.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         while (qryIdx < S.size() && L[queries[qryIdx]] >= i) {
      |                ~~~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5100 KB Output is correct
2 Correct 6 ms 5100 KB Output is correct
3 Correct 6 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 10 ms 5100 KB Output is correct
7 Correct 7 ms 5100 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 6 ms 5100 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5100 KB Output is correct
2 Correct 6 ms 5100 KB Output is correct
3 Correct 6 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 10 ms 5100 KB Output is correct
7 Correct 7 ms 5100 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 6 ms 5100 KB Output is correct
10 Execution timed out 4070 ms 6004 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5100 KB Output is correct
2 Correct 6 ms 5100 KB Output is correct
3 Correct 6 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 10 ms 5100 KB Output is correct
7 Correct 7 ms 5100 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 6 ms 5100 KB Output is correct
10 Execution timed out 4070 ms 6004 KB Time limit exceeded
11 Halted 0 ms 0 KB -