oj.uz

답안 #318788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
318788 2020-11-03T08:33:03 Z Vladth11 늑대인간 (IOI18_werewolf) C++14
0 / 100
 1100 ms 142808 KB 
#include <bits/stdc++.h>
//#include "werewolf.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;

const ll NMAX = 400001;
const int INF = 2e9;
const ll MOD = 998244353;
const ll p = 31;
const ll BLOCK = 101;
const ll nr_of_bits = 20;

vector <int> init[NMAX];

class Arbore {
    int parent[NMAX];
    vector <int> v[NMAX];
    int stamp = 0;
public:
        pii timp[NMAX];

    int dp[NMAX][nr_of_bits];
    vector <int> parcurgere;
    int n;
    void Init(int _n) {
        n = _n;
        parcurgere.push_back(0);
        for(int i = 0; i <= n + 1; i++) {
            parent[i] = 0;
        }
    }
    int root(int x) {
        if(parent[x] == 0)
            return x;
        return (parent[x] = root(parent[x]));
    }
    void merge(int a, int b) {
        a = root(a);
        if(a == b)
            return;
        parent[a] = b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    void DFS(int node, int p) {
        timp[node].first = ++stamp;
        dp[node][0] = p;
        parcurgere.push_back(node);
        for(auto x : v[node]) {
            if(x == p)
                continue;
            DFS(x, node);
        }
        timp[node].second = stamp;
    }
    void Precalc() {
        for(int j = 1; j < nr_of_bits; j++) {
            for(int i = 1; i <= n; i++) {
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
            }
        }
    }
} C, D;

class AIB{
    int aib[NMAX], n;
public:
    void Init(int _n){
        n = _n + 1;
    }
    void update(int x){
        for(int i = x; i < n; i += i&(-i)){
            aib[i]++;
        }
    }
    int query(int x){
        int s = 0;
        for(int i = x; i > 0; i -= i&(-i)){
            s += aib[i];
        }
        return s;
    }
}aib;

vector <pii> queries[NMAX];
vector <int> Compute(int Q) {
    vector <int> rez(Q);
    map <int, int> mp;
    for(int i = 1; i < D.parcurgere.size(); i++){
        mp[D.parcurgere[i]] = i;
        //debug_with_space(D.parcurgere[i]);
    }
    //debug(Q);

    aib.Init(NMAX - 1);
    int i;
    for(int i = 1; i <= C.n; i++){
        aib.update(mp[C.parcurgere[i]]);
       // debug(mp[C.parcurgere[i]]);
        for(auto x : queries[i]){
            int c = x.second;
            if(c < 0)
                c = -1;
            else
                c = 1;
            rez[c * x.second] += c * aib.query(x.first);
        }
    }
    for(i = 0; i < Q; i++){
        rez[i] = (rez[i] > 0);
    }
    return rez;
}


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();
    vector<int> A(Q);
    int i;
    for(i = 0; i < X.size(); i++) {
        init[X[i] + 1].push_back(Y[i] + 1);
        init[Y[i] + 1].push_back(X[i] + 1);
    }
    C.Init(N);
    D.Init(N);
    for(int i = N; i >= 1; i--) {
        for(auto x : init[i]) {
            if(x > i) {
                C.merge(x, i);
               // break;
            }
        }
    }
    for(int i = 1; i <= N; i++) {
        for(auto x : init[i]) {
            if(x < i) {
                D.merge(x, i);
               // break;
            }
        }
    }
    C.DFS(1, 0);
    //debug(N);
    D.DFS(N, 0);
    C.Precalc();
    D.Precalc();
    for(i = 0; i < Q; i++) {
        S[i]++;
        E[i]++;
        int r = S[i], pas = nr_of_bits - 1;
        while(pas >= 0) {
            int nou = C.dp[r][pas];
            if(nou != 0 && nou >= L[i])
                r = nou;
            pas--;
        }
        int r1 = r;
        pii a = {C.timp[r].first, C.timp[r].second};
        r = E[i], pas = nr_of_bits - 1;
        while(pas >= 0) {
            int nou = D.dp[r][pas];
            if(nou != 0 && nou <= R[i])
                r = nou;
            pas--;
        }
        if(r1 < L[i])
            continue;
        if(r > R[i])
            continue;
        pii b = {D.timp[r].first, D.timp[r].second};
        int x1 = a.first, x2 = a.second, y1 = b.first, y2 = b.second;
        queries[x1 - 1].push_back({y1 - 1, i});
        queries[x1 - 1].push_back({y2, -i});
        queries[x2].push_back({y2, i});
        queries[x2].push_back({y1 - 1, -i});
    }
    A = Compute(Q);
    return A;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> Compute(int)':
werewolf.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 1; i < D.parcurgere.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
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:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(i = 0; i < X.size(); i++) {
      |                ~~^~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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