Submission #116232

#	Time	Username	Problem	Language	Result	Execution time	Memory
116232		zubec	Werewolf (IOI18_werewolf)	C++14	100 / 100	1236 ms	104564 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 200100;

vector <vector <int> > g, g1, g2;

int dsu[2][N], fenw[N], n;

int tin[2][N], tout[2][N], tiktak, up[2][20][N], pos[N];

int dsu_get(int pr, int v){
    if (v == dsu[pr][v])
        return v;
    return dsu[pr][v] = dsu_get(pr, dsu[pr][v]);
}

void upd(int v){
    for (int i = v; i <= n; i += (i & (-i))){
        ++fenw[i];
    }
}

int get(int v){
    int ans = 0;
    for (int i = v; i >= 1; i -= (i & (-i))){
        ans += fenw[i];
    }
    return ans;
}

void dfs(vector <vector <int> > &g, int cur, int v, int p){
    tin[cur][v] = ++tiktak;
    up[cur][0][v] = p;
    for (int i = 1; i < 20; i++){
        up[cur][i][v] = up[cur][i-1][up[cur][i-1][v]];
    }
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        dfs(g, cur, to, v);
    }
    tout[cur][v] = tiktak;
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    n = N;
    g.resize(n);
    g1.resize(n);
    g2.resize(n);
    for (int i = 0; i <= n; i++){
        dsu[0][i] = dsu[1][i] = i;
        fenw[i] = 0;
    }
    int Q = S.size();
    vector<int> A(Q);

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

    for (int i = n-1; i >= 0; i--){
        for (int j = 0; j < g[i].size(); j++){
            int to = g[i][j];
            if (to < i)
                continue;
            int a = dsu_get(0, i);
            int b = dsu_get(0, to);
            if (a == b)
                continue;
            dsu[0][b] = a;
            g1[a].push_back(b);
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < g[i].size(); j++){
            int to = g[i][j];
            if (i < to)
                continue;
            int a = dsu_get(1, i);
            int b = dsu_get(1, to);
            if (a == b)
                continue;
            dsu[1][b] = a;
            g2[a].push_back(b);
        }
    }
    tiktak = 0;
    dfs(g1, 0, dsu_get(0, 0), dsu_get(0, 0));
    tiktak = 0;
    dfs(g2, 1, dsu_get(1, 0), dsu_get(1, 0));

    vector <pair<int, pair<int, int> > > zapr;

    for (int i = 0; i < Q; i++){
        int s = S[i], e = E[i], l = L[i], r = R[i];
        for (int i = 19; i >= 0; i--){
            if (up[0][i][s] >= l)
                s = up[0][i][s];
            if (up[1][i][e] <= r)
                e = up[1][i][e];
        }
        zapr.push_back({tin[0][s]-1, {-(i+1), e} });
        zapr.push_back({tout[0][s], {(i+1), e}});
    }
    for (int i = 0; i < n; i++){
        pos[tin[0][i]-1] = tin[1][i];
    }
    sort(zapr.begin(), zapr.end());
    int ptr = 0;
    for (int i = 0; i < zapr.size(); i++){
        int tim = zapr[i].first, id = zapr[i].second.first, v = zapr[i].second.second;
        while(ptr < tim){
            upd(pos[ptr]);
            ++ptr;
        }
        if (id < 0)
            A[abs(id)-1] -= (get(tout[1][v])-get(tin[1][v]-1)); else
            A[abs(id)-1] += (get(tout[1][v])-get(tin[1][v]-1));
    }
    for (int i = 0; i < Q; i++){
        A[i] = (A[i] > 0);
    }


    return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(std::vector<std::vector<int> >&, int, int, int)':
werewolf.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].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:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); i++){
                     ~~^~~~~~~~~~
werewolf.cpp:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[i].size(); j++){
                         ~~^~~~~~~~~~~~~
werewolf.cpp:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[i].size(); j++){
                         ~~^~~~~~~~~~~~~
werewolf.cpp:114:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < zapr.size(); i++){
                     ~~^~~~~~~~~~~~~

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