제출 #318795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318795		Vladth11	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1209 ms	132828 KiB

werewolf

#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 = 200001;
const int INF = 2e9;
const ll MOD = 998244353;
const ll p = 31;
const ll BLOCK = 101;
const ll nr_of_bits = 18;

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 + 1, 0);
    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(D.n);
    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 + 1] > 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]++;
        R[i]++;
        E[i]++;
        L[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--;
        }
        if(r < L[i])
            continue;
        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(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 + 1});
        queries[x1 - 1].push_back({y2, -i - 1});
        queries[x2].push_back({y2, i + 1});
        queries[x2].push_back({y1 - 1, -i - 1});
    }
    A = Compute(Q);
    A.pop_back();
    return A;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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