Submission #120116

#	Time	Username	Problem	Language	Result	Execution time	Memory
120116		Meloric	Werewolf (IOI18_werewolf)	C++14	100 / 100	2448 ms	169576 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
#define ub upper_bound
#define lb lower_bound

using namespace std;

struct disj{
    vector<int> par;
    disj(int n){
        for(int i = 0; i<n; i++)par.pb(i);
    }
    int fi(int a){return (a == par[a]) ? a : par[a] = fi(par[a]);}
    void me(int a, int b){
        a = fi(a);
        b = fi(b);
        par[b] = a;
    }
};
struct ft{
    vector<int> fen;
    ft(int n){
        fen.assign(n+1, 0);
    }
    int qer(int a){
        a++;
        int ans = 0;
        for(; a > 0; a-=a&(-a))ans+=fen[a];
        return ans;
    }
    void upd(int a, int b){
        a++;
        for(; a < fen.size(); a+=a&(-a))fen[a]+=b;
    }
};
void print(vector<vector<int>>& g2){
    int k = 0;
    for(auto i : g2){
        cout << k <<':';k++;
        for(auto j : i){
            cout << j << ' ';
        }
        cout << '\n';
    }
}
void dfs(int v, int p, int& counter, vector<vector<int>>& g, vector<vector<int>>& up, vector<pii>& time){
    up[v][0] = p;
    time[v].X = counter++;
    for(int i = 1; i < 30; i++){
        up[v][i] = up[up[v][i-1]][i-1];
    }
    for(auto ch : g[v])dfs(ch, v, counter, g, up, time);
    time[v].Y = counter++;
}
int jump1(int v, int val, vector<vector<int>>& up){
    for(int i = 29; i >= 0; i--){
        if(up[v][i] <= val){
            v = up[v][i];
        }
    }
    return v;
}
int jump2(int v, int val, vector<vector<int>>& up){
    for(int i = 29; i >= 0; i--){
        if(up[v][i] >= val){
            v = up[v][i];
        }
    }
    return v;
}
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(); int M = X.size();
    vector<vector<int>> g;
    g.assign(N, vector<int>());
    for(int i = 0; i<M; i++){
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);
    }
    disj sml(N), big(N);
    vector<vector<int>> g1, g2, up1, up2;
    vector<pii> time1, time2;
    g1.assign(N, vector<int>());
    g2.assign(N, vector<int>());
    up1.assign(N, vector<int>(30));
    up2.assign(N, vector<int>(30));
    time1.assign(N, {0, 0});
    time2.assign(N, {0, 0});
    for(int i = 0; i < N; i++){
        for(auto j : g[i]){
            if(j < i && big.fi(i) != big.fi(j)){
                g1[i].pb(big.fi(j));
                big.me(i, j);
            }
        }
    }
    for(int i = N-1; i >= 0; i--){
        for(auto j : g[i]){
            if(j > i && sml.fi(i) != sml.fi(j)){
                g2[i].pb(sml.fi(j));
                sml.me(i, j);
            }
        }
    }
    int counter = 0;
    dfs(N-1, N-1, counter, g1, up1, time1);counter = 0;
    dfs(0, 0, counter, g2, up2, time2);
    vector<vector<int>> events;
    for(int i = 0; i< N; i++){
        events.pb({time1[i].X, 0, time2[i].X, -1, -1});
    }
    for(int i = 0; i< Q; i++){
        int tmp1 = jump1(E[i], R[i], up1);
        int tmp2 = jump2(S[i], L[i], up2);
        events.pb({time1[tmp1].X, -1, time2[tmp2].X, time2[tmp2].Y, i});
        events.pb({time1[tmp1].Y, 1, time2[tmp2].X, time2[tmp2].Y, i});
    }
    //print(events);
    sort(events.begin(), events.end());
    ft fen(2*N+5);
    vector<int> A(Q);
    for(auto i : events){
        if(i[1] == 0){
            fen.upd(i[2], 1);
        }else{
            int ans = fen.qer(i[3])-fen.qer(i[2]-1);
            A[i[4]] += ans*i[1];
        }
    }
    //for(auto i : A)cout << i << ' ';
    for (int i = 0; i < Q; ++i){
        if(A[i]>0)A[i] = 1;
    }
    return A;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void ft::upd(int, int)':
werewolf.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; a < fen.size(); a+=a&(-a))fen[a]+=b;
               ~~^~~~~~~~~~~~

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