oj.uz

답안 #100484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100484 2019-03-11T14:53:57 Z jeff 늑대인간 (IOI18_werewolf) C++14
15 / 100
 1176 ms 74412 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

int N, A[800000], id[400000], f[200000], l[2][2][200000], 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

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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 19200 KB Output is correct
2 Correct 20 ms 19200 KB Output is correct
3 Correct 20 ms 19200 KB Output is correct
4 Correct 22 ms 19192 KB Output is correct
5 Correct 19 ms 19144 KB Output is correct
6 Correct 22 ms 19200 KB Output is correct
7 Correct 21 ms 19172 KB Output is correct
8 Correct 23 ms 19200 KB Output is correct
9 Correct 22 ms 19200 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 19200 KB Output is correct
2 Correct 20 ms 19200 KB Output is correct
3 Correct 20 ms 19200 KB Output is correct
4 Correct 22 ms 19192 KB Output is correct
5 Correct 19 ms 19144 KB Output is correct
6 Correct 22 ms 19200 KB Output is correct
7 Correct 21 ms 19172 KB Output is correct
8 Correct 23 ms 19200 KB Output is correct
9 Correct 22 ms 19200 KB Output is correct
10 Correct 26 ms 20224 KB Output is correct
11 Correct 30 ms 20224 KB Output is correct
12 Correct 29 ms 20088 KB Output is correct
13 Correct 30 ms 20472 KB Output is correct
14 Correct 29 ms 20288 KB Output is correct
15 Correct 29 ms 20224 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1176 ms 74412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 19200 KB Output is correct
2 Correct 20 ms 19200 KB Output is correct
3 Correct 20 ms 19200 KB Output is correct
4 Correct 22 ms 19192 KB Output is correct
5 Correct 19 ms 19144 KB Output is correct
6 Correct 22 ms 19200 KB Output is correct
7 Correct 21 ms 19172 KB Output is correct
8 Correct 23 ms 19200 KB Output is correct
9 Correct 22 ms 19200 KB Output is correct
10 Correct 26 ms 20224 KB Output is correct
11 Correct 30 ms 20224 KB Output is correct
12 Correct 29 ms 20088 KB Output is correct
13 Correct 30 ms 20472 KB Output is correct
14 Correct 29 ms 20288 KB Output is correct
15 Correct 29 ms 20224 KB Output is correct
16 Incorrect 1176 ms 74412 KB Output isn't correct
17 Halted 0 ms 0 KB -