oj.uz

답안 #434474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
434474 2021-06-21T10:50:48 Z dxz05 늑대인간 (IOI18_werewolf) C++14
0 / 100
 4000 ms 58288 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 4e5 + 3e2;

vector<int> g[MAXN];

bool used[MAXN];
int tin[MAXN];
vector<int> vec;
void dfs(int v){
    used[v] = true;
    vec.push_back(v);
    tin[v] = vec.size();

    for (int u : g[v]){
        if (!used[u]){
            dfs(u);
        }
    }

}

#define MP make_pair
#define PII pair<int, int>

PII t[4 * MAXN];

PII combine(PII lf, PII rg){
    return MP(min(lf.first, rg.first), max(lf.second, rg.second));
}

void build(int v, int tl, int tr){
    if (tl == tr){
        t[v].first = t[v].second = vec[tl];
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);

    t[v] = combine(t[v + v], t[v + v + 1]);
}

PII get(int v, int tl, int tr, int l, int r){
    if (l <= tl && tr <= r) return t[v];
    if (tl > r || tr < l) return MP(1e9, -1e9);
    int tm = (tl + tr) >> 1;
    return combine(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));
}

PII get_positions(int X, int N, int L, int R){
    X = tin[X] - 1;
    int lf = X, rg = X;

    int l = 0, r = X;
    while (l <= r){
        int m = (l + r) >> 1;
        PII f = get(1, 0, N - 1, m, X);
        if (f.first >= L && f.second <= R){
            lf = l;
            r = m - 1;
        } else l = m + 1;
    }

    l = X, r = N - 1;
    while (l <= r){
        int m = (l + r) >> 1;
        PII f = get(1, 0, N - 1, X, m);
        if (f.first >= L && f.second <= R){
            rg = l;
            l = m + 1;
        } else r = m - 1;
    }

    return MP(lf, rg);
}

int smaller[MAXN];

int fw[MAXN];
void add(int x, int y){
    while (x < MAXN){
        fw[x] += y;
        x += (-x & x);
    }
}

int get(int x){
    int ret = 0;
    while (x > 0){
        ret += fw[x];
        x -= (-x & x);
    }
    return ret;
}

vector<pair<PII, PII>> queries[MAXN];

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int Q = S.size(), M = X.size();
    vector<int> A(Q, 0);

    for (int i = 0; i < M; i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    for (int i = 0; i < N; i++){
        if (g[i].size() == 1){
            dfs(i);
            break;
        }
    }


    build(1, 0, N - 1);

    for (int i = 0; i < Q; i++){
        PII fs = get_positions(S[i], N, L[i], N - 1), fe = get_positions(E[i], N, 0, R[i]);
        int l1 = fs.first, r1 = fs.second, l2 = fe.first, r2 = fe.second;

        //cout << "\t" << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;

        int l = max(l1, l2), r = min(r1, r2);
        if (L[i]) queries[L[i] - 1].emplace_back(MP(i, 0), MP(l, r));
        queries[R[i]].emplace_back(MP(i, 1), MP(l, r));
    }

    for (int i = 0; i < N; i++){
        add(tin[i], 1);

        for (auto qu : queries[i]){
            int ind = qu.first.first, ty = qu.first.second, l = qu.second.first, r = qu.second.second;
           // cout << i << ' ' << l << ' ' << r << endl;
            int res = get(r + 1) - get(l);

            if (ty == 0) A[ind] -= res; else
                A[ind] += res;

        }

    }

    for (int i = 0; i < Q; i++) A[i] = A[i] > 0;

    return A;
}

/**
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4


6 5 1
2 0
0 1
3 5
1 3
5 4
1 4 0 4

*/

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4089 ms 58288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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