Submission #200001

#	Time	Username	Problem	Language	Result	Execution time	Memory
200001		jeff	Werewolf (IOI18_werewolf)	C++14	100 / 100	962 ms	100064 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
 
int N, A[800000], id[400000], f[200000], l[2][2][400000], y, z;
pair<int, int> B[800000];
vector<int> adj[2][400000], rs;
vector<pair<int, int> > v;
vector<tuple<int, int, int, int, int> > qr;
 
inline int frt(int i) {return i == id[i] ? i : id[i] = frt(id[i]);}
 
inline void ufds(int t, int a, int b) {
    a = frt(a);
    b = frt(b);
    if (a == b) return;
    adj[t][a].push_back(y);
    adj[t][b].push_back(y);
    adj[t][y].push_back(a);
    adj[t][y].push_back(b);
    id[a] = id[b] = y++;
}
 
void it(int t, int i, int o) {
    l[t][0][i] = z;
    for (int j = 0; j < adj[t][i].size(); ++j) if (o != adj[t][i][j]) it(t, adj[t][i][j], i);
    if (i < N) {
        if (!t) f[z++] = i;
        else ++z;
    }
    l[t][1][i] = z - 1;
}
 
void init(int i, int a, int b) {
    A[i] = INT_MAX;
    B[i] = make_pair(a, b);
    if (a >= b) return;
    init(i * 2, a, (a + b) / 2);
    init(i * 2 + 1, (a + b) / 2 + 1, b);
}
 
int q(int i, int a, int b) {
    if (b < B[i].first || B[i].second < a) return INT_MAX;
    if (a <= B[i].first && B[i].second <= b) return A[i];
    return min(q(i * 2, a, b), q(i * 2 + 1, a, b));
}
 
void u(int i, int p, int v) {
    if (p < B[i].first || B[i].second < p) return;
    if (p <= B[i].first && B[i].second <= p) {A[i] = v; return;}
    u(i * 2, p, v);
    u(i * 2 + 1, p, v);
    A[i] = min(A[i * 2], A[i * 2 + 1]);
}
 
vector<int> check_validity(int _N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    N = _N;
    int M = X.size(), Q = S.size(), i, j;
    rs.assign(Q, 0);
    for (i = 0; i < Q; ++i) qr.emplace_back(R[i], L[i], E[i], S[i], i);
    for (i = 0; i < M; ++i) v.emplace_back(max(X[i], Y[i]), min(X[i], Y[i]));
    sort(v.begin(), v.end());
    sort(qr.begin(), qr.end());
    iota(id, id + N * 2 - 1, 0);
    y = N;
    for (i = j = 0; i < M; ++i) {
        while (j < Q && get<0>(qr[j]) < v[i].first) get<2>(qr[j]) = frt(get<2>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j;
        ufds(0, v[i].first, v[i].second);
        swap(v[i].first, v[i].second);
    }
    while (j < Q) get<3>(qr[j]) = frt(get<3>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j;
    sort(v.begin(), v.end());
    sort(qr.begin(), qr.end());
    iota(id, id + N * 2 - 1, 0);
    y = N;
    for (i = M - 1, j = Q - 1; i > -1; --i) {
        while (j > -1 && get<0>(qr[j]) > v[i].first) get<3>(qr[j]) = frt(get<3>(qr[j])), --j;
        ufds(1, v[i].first, v[i].second);
    }
    while (j > -1) get<2>(qr[j]) = frt(get<2>(qr[j])), --j;
    it(0, N * 2 - 2, -1);
    z = 0;
    it(1, N * 2 - 2, -1);
    for (i = 0; i < Q; ++i) get<0>(qr[i]) = l[0][0][get<2>(qr[i])], get<1>(qr[i]) = l[0][1][get<2>(qr[i])];
    sort(qr.begin(), qr.end());
    init(1, 0, N - 1);
    for (i = Q - 1, j = N - 1; i > -1; --i) {
        while (j >= get<0>(qr[i])) u(1, l[1][0][f[j]], j), --j;
        rs[get<4>(qr[i])] = q(1, l[1][0][get<3>(qr[i])], l[1][1][get<3>(qr[i])]) <= get<1>(qr[i]);
    }
    return rs;
}

Compilation message (stderr)

werewolf.cpp: In function 'void it(int, int, int)':
werewolf.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[t][i].size(); ++j) if (o != adj[t][i][j]) it(t, adj[t][i][j], i);
                     ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51