Submission #185429

#	Time	Username	Problem	Language	Result	Execution time	Memory
185429		alexandra_udristoiu	Werewolf (IOI18_werewolf)	C++14	34 / 100	818 ms	524288 KiB

werewolf

#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>
#include "werewolf.h"
#define DIM 200005
#define f first
#define s second
using namespace std;
static int n, q, nr;
static int t[DIM], aint[4 * DIM], d[DIM];
static pair<int, int> p[2][DIM];
static vector<int> v[DIM], vt[2][DIM], sol;
struct str{
    int ind, x, y, st, dr, p1, u1, p2, u2;
};
static str w[DIM];
int cmp1(str a, str b){
    return a.st > b.st;
}
int cmp2(str a, str b){
    return a.dr < b.dr;
}
int cmp3(str a, str b){
    return a.p1 > b.p1;
}
int rad(int x){
    int y, aux;
    y = x;
    while(t[y] != 0){
        y = t[y];
    }
    while(t[x] != 0){
        aux = t[x];
        t[x] = y;
        x = aux;
    }
    return y;
}
void update(int nod, int st, int dr, int p, int val){
    if(st == dr){
        aint[nod] = val;
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update(2 * nod, st, mid, p, val);
        }
        else{
            update(2 * nod + 1, mid + 1, dr, p, val);
        }
        aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
    }
}
int query(int nod, int st, int dr, int p, int u){
    if(p <= st && dr <= u){
        return aint[nod];
    }
    else{
        int mid = (st + dr) / 2;
        int x, y;
        x = y = n + 1;
        if(p <= mid){
            x = query(2 * nod, st, mid, p, u);
        }
        if(u > mid){
            y = query(2 * nod + 1, mid + 1, dr, p, u);
        }
        return min(x, y);
    }
}
void dfs(int nod, int ind){
    p[ind][nod].f = ++nr;
    for(int i = 0; i < vt[ind][nod].size(); i++){
        dfs(vt[ind][nod][i], ind);
    }
    p[ind][nod].s = nr;
}
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 i, j, nod, u, r;
    n = N;
    q = S.size();
    sol.resize(q);
    for(i = 0; i < n - 1; i++){
        X[i]++; Y[i]++;
        v[ X[i] ].push_back(Y[i]);
        v[ Y[i] ].push_back(X[i]);
    }
    for(i = 0; i < q; i++){
        w[i + 1] = {i, S[i] + 1, E[i] + 1, L[i] + 1, R[i] + 1, 0, 0, 0, 0};
    }
    sort(w + 1, w + q + 1, cmp1);
    u = 1;
    for(i = n; i >= 1; i--){
        for(j = 0; j < v[i].size(); j++){
            nod = v[i][j];
            r = rad(nod);
            if(nod > i && r != i){
                t[r] = i;
                vt[0][i].push_back(r);
            }
        }
        while(w[u].st == i){
            w[u].p1 = rad(w[u].x);
            u++;
        }
    }
    memset(t, 0, sizeof(t) );
    sort(w + 1, w + q + 1, cmp2);
    u = 1;
    for(i = 1; i <= n; i++){
        for(j = 0; j < v[i].size(); j++){
            nod = v[i][j];
            r = rad(nod);
            if(nod < i && r != i){
                t[r] = i;
                vt[1][i].push_back(r);
            }
        }
        while(w[u].dr == i){
            w[u].p2 = rad(w[u].y);
            u++;
        }
    }
    dfs(1, 0);
    nr = 0;
    dfs(n, 1);
    for(i = 1; i <= n; i++){
        d[ p[0][i].f ] = i;
    }
    for(i = 1; i <= q; i++){
        nod = w[i].p1;
        w[i].p1 = p[0][nod].f;
        w[i].u1 = p[0][nod].s;
        nod = w[i].p2;
        w[i].p2 = p[1][nod].f;
        w[i].u2 = p[1][nod].s;
    }
    sort(w + 1, w + q + 1, cmp3);
    u = 1;
    for(i = 1; i <= 4 * n; i++){
        aint[i] = n + 1;
    }
    for(i = n; i >= 1; i--){
        update(1, 1, n, p[1][ d[i] ].f, i);
        while(w[u].p1 == i){
            if( query(1, 1, n, w[u].p2, w[u].u2) <= w[u].u1){
                sol[ w[u].ind ] = 1;
            }
            else{
                sol[ w[u].ind ] = 0;
            }
            u++;
        }
    }
    return sol;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vt[ind][nod].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:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j = 0; j < v[i].size(); j++){
                    ~~^~~~~~~~~~~~~
werewolf.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j = 0; j < v[i].size(); j++){
                    ~~^~~~~~~~~~~~~

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