Submission #82793

#	Time	Username	Problem	Language	Result	Execution time	Memory
82793		zubec	Werewolf (IOI18_werewolf)	C++14	0 / 100	1130 ms	95572 KiB

werewolf

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

const int N = 200100;

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

int a[N], pos[N], n, dsu[2][N], up[2][20][N], tiktak, tin[2][N], tout[2][N], fenw[N];

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

void dfs(vector <vector <int> > &g, int cur, int v, int p){
    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]];
    tin[cur][v] = ++tiktak;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        dfs(g, cur, to, v);
    }
    tout[cur][v] = tiktak;
}

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;
}

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;
    for (int i = 0; i < n; i++){
        dsu[0][i] = dsu[1][i] = i;
        fenw[i] = 0;
    }
    g.resize(n);
    g1.resize(n);
    g2.resize(n);
    vector <int> A((int)S.size(), 0);
    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 (i > to)
                continue;
            int a = dsu_get(i, 0);
            int b = dsu_get(to, 0);
            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(i, 1);
            int b = dsu_get(to, 1);
            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(0, 1), dsu_get(0, 1));
    //return A;
    vector <pair<int, pair<int, int> > > zapr;
    for (int i = 0; i < S.size(); 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, e}});
        zapr.push_back({tout[0][s], {i, 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 curTim = zapr[i].first, id = zapr[i].second.first, v = zapr[i].second.second;
        while(ptr < curTim){
            upd(pos[ptr]);
            ++ptr;
        }

        if (id < 0){
            A[abs(id)] -= (get(tout[1][v])-get(tin[1][v]-1));
        } else {
            A[abs(id)] += (get(tout[1][v])-get(tin[1][v]-1));
        }

    }
    for (int i = 0; i < A.size(); 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

*/

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(std::vector<std::vector<int> >&, int, int, int)':
werewolf.cpp:22: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:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); i++){
                     ~~^~~~~~~~~~
werewolf.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[i].size(); j++){
                         ~~^~~~~~~~~~~~~
werewolf.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[i].size(); j++){
                         ~~^~~~~~~~~~~~~
werewolf.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < S.size(); i++){
                     ~~^~~~~~~~~~
werewolf.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < zapr.size(); i++){
                     ~~^~~~~~~~~~~~~
werewolf.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < A.size(); i++)
                     ~~^~~~~~~~~~

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