oj.uz

Submission #120438

# Submission time Handle Problem Language Result Execution time Memory
120438 2019-06-24T13:20:04 Z songc Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 44928 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, Q;
int P[404040], NL[404040], NR[404040], num;
int H[202020], W[202020];
int HS[202020], HE[202020];
int WS[202020], WE[202020];
vector<int> ans, C[404040];
vector<pii> Point;

struct Data{
    int t, u, v, w;
};
vector<Data> A;

int Find(int u){
    if (u == P[u]) return u;
    return P[u] = Find(P[u]);
}

void Union(int u, int v){
    int pu = Find(u);
    int pv = Find(v);
    if (pu == pv) return;
    P[pu] = P[pv] = num;
    NL[num] = NL[pu];
    NR[num] = NR[pv];
    C[num].push_back(pu);
    C[num].push_back(pv);
    num++;
}

void dfsH(int u){
    if (C[u].empty()){
        H[u] = num++;
        return;
    }
    dfsH(C[u][0]);
    dfsH(C[u][1]);
    C[u].clear();
}

void dfsW(int u){
    if (C[u].empty()){
        W[u] = num++;
        return;
    }
    dfsW(C[u][0]);
    dfsW(C[u][1]);
    C[u].clear();
}

struct Node{
    Node *lc, *rc;
    int val=0;
} *PST[202020];

void init(Node* now, int s, int e){
    if (s == e) return;
    int mid = (s+e)/2;
    now->lc = new Node;
    init(now->lc, s, mid);
    now->rc = new Node;
    init(now->rc, mid+1, e);
}

void update(Node* pre, Node* now, int s, int e, int t){
    now->val++;
    if (s == e) return;
    int mid = (s+e)/2;
    if (t <= mid){
        now->lc = new Node;
        update(pre->lc, now->lc, s, mid, t);
        now->rc = pre->rc;
    }
    else{
        now->lc = pre->lc;
        now->rc = new Node;
        update(pre->rc, now->rc, mid+1, e, t);
    }
}

int query(Node* now, int s, int e, int ts, int te){
    if (e < ts || te < s) return 0;
    if (ts <= s && e <= te) return now->val;
    int mid = (s+e)/2;
    return query(now->lc, s, mid, ts, te) + query(now->rc, mid+1, e, ts, te);
}

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, M = X.size(), Q = S.size();

    for (int i=0; i<M; i++) A.push_back((Data){0, X[i], Y[i], min(X[i], Y[i])});
    for (int i=0; i<Q; i++) A.push_back((Data){1, S[i], i, L[i]});
    sort(A.begin(), A.end(), [&](Data a, Data b){
        if (a.w == b.w) return a.t < b.t;
        return a.w > b.w;
    });

    num = N+1;
    for (int i=0; i<=2*N; i++) P[i] = i, NL[i] = NR[i] = i;
    for (int i=0; i<(int)A.size(); i++){
        if (A[i].t == 0) Union(A[i].u, A[i].v);
        else {
            HS[A[i].v] = NL[Find(A[i].u)];
            HE[A[i].v] = NR[Find(A[i].u)];
        }
    }
    num=0;
    dfsH(2*N-1);
    A.clear();

    for (int i=0; i<M; i++) A.push_back((Data){0, X[i], Y[i], max(X[i], Y[i])});
    for (int i=0; i<Q; i++) A.push_back((Data){1, E[i], i, R[i]});
    sort(A.begin(), A.end(), [&](Data a, Data b){
        if (a.w == b.w) return a.t < b.t;
        return a.w < b.w;
    });

    num = N+1;
    for (int i=0; i<=2*N; i++) P[i] = i, NL[i] = NR[i] = i;
    for (int i=0; i<(int)A.size(); i++){
        if (A[i].t == 0) Union(A[i].u, A[i].v);
        else {
            WS[A[i].v] = NL[Find(A[i].u)];
            WE[A[i].v] = NR[Find(A[i].u)];
        }
    }
    num=0;
    dfsW(2*N-1);
    A.clear();

    for (int i=0; i<Q; i++){
        HS[i] = H[HS[i]], HE[i] = H[HE[i]];
        WS[i] = W[WS[i]], WE[i] = W[WE[i]];
    }
    for (int i=0; i<N; i++) Point.push_back(pii(H[i], W[i]));
    sort(Point.begin(), Point.end());
    /*
    PST[0] = new Node;
    init(PST[0], 1, N);
    for (int i=1; i<=N; i++) {
        PST[i] = new Node;
        update(PST[i-1], PST[i], 1, N, Point[i].second+1);
    }
    */

    for (int i=0; i<Q; i++){
        //if (query(PST[HE[i]+1], 1, N, WS[i]+1, WE[i]+1) - query(PST[HS[i]+1], 1, N, WS[i]+1, WE[i]+1)) ans.push_back(1);
        //else ans.push_back(0);
        bool tf = false;
        for (int j=0; j<N; j++){
            if (HS[i] <= Point[j].first && Point[j].first <= HE[i] && WS[i] <= Point[j].second && Point[j].second <= WE[i]) tf = true;
        }
        if (tf) ans.push_back(1);
        else ans.push_back(0);
    }
    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9856 KB Output is correct
2 Correct 10 ms 9856 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Correct 11 ms 9856 KB Output is correct
8 Correct 11 ms 9856 KB Output is correct
9 Correct 11 ms 9856 KB Output is correct
10 Correct 31 ms 10624 KB Output is correct
11 Correct 29 ms 10496 KB Output is correct
12 Correct 23 ms 10496 KB Output is correct
13 Correct 33 ms 10596 KB Output is correct
14 Correct 24 ms 10624 KB Output is correct
15 Correct 26 ms 10620 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9856 KB Output is correct
2 Correct 10 ms 9856 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Correct 11 ms 9856 KB Output is correct
8 Correct 11 ms 9856 KB Output is correct
9 Correct 11 ms 9856 KB Output is correct
10 Correct 31 ms 10624 KB Output is correct
11 Correct 29 ms 10496 KB Output is correct
12 Correct 23 ms 10496 KB Output is correct
13 Correct 33 ms 10596 KB Output is correct
14 Correct 24 ms 10624 KB Output is correct
15 Correct 26 ms 10620 KB Output is correct
16 Execution timed out 4085 ms 44928 KB Time limit exceeded
17 Halted 0 ms 0 KB -