Submission #393327

#	Time	Username	Problem	Language	Result	Execution time	Memory
393327		BartolM	Werewolf (IOI18_werewolf)	C++17	100 / 100	1033 ms	110764 KiB

werewolf

#define DEBUG 0
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <pii, pii> ppp;

const int INF=0x3f3f3f3f;
const int N=2e5+5;

int n, m, q, uk, dt;
int P[2*N], roots[N], lef[2*N], rig[2*N], F[2*N];
vector <int> ls[N], dj[2*N], toc[2*N], sol;
vector <pii> que[N];
vector <ppp> duz[2*N];
pii p[N], r_x[N], r_y[N];

int query(int x) {
    int ret=0;
    for (x++; x>0; x-=x&-x) ret+=F[x];
    return ret;
}

void update(int x, int val) {
    for (x++; x<=2*n+2; x+=x&-x) F[x]+=val;
}

int name(int x) {
    if (x==P[x]) return x;
    P[x]=name(P[x]);
    return P[x];
}

void dfs(int node) {
    lef[node]=dt++;
    for (int sus:dj[node]) dfs(sus);
    rig[node]=dt-1;
}

vector<int> check_validity(int NN, vector<int> XX, vector<int> YY,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n=NN;
    m=XX.size();
    q=L.size();
    for (int i=0; i<m; ++i) ls[XX[i]].pb(YY[i]), ls[YY[i]].pb(XX[i]);

    for (int i=0; i<2*n; ++i) P[i]=i;
    for (int i=0; i<q; ++i) que[L[i]].pb(mp(S[i], i));
    uk=n;
    for (int i=n-1; i>=0; --i) {
        dj[uk].pb(name(i));
        #if DEBUG
            printf("dijete od %d je %d\n", uk, name(i));
        #endif // DEBUG
        P[name(i)]=uk;
        for (int sus:ls[i]) {
            if (sus<=i || name(sus)==uk) continue;
            #if DEBUG
                printf("dijete od %d je %d\n", uk, name(sus));
            #endif // DEBUG
            dj[uk].pb(name(sus));
            P[name(sus)]=uk;
        }
        uk++;
        for (pii pp:que[i]) roots[pp.Y]=name(pp.X);
    }
    dt=0;
    dfs(name(0));
    for (int i=0; i<n; ++i) p[i].X=lef[i];
    for (int i=0; i<q; ++i) r_x[i]=mp(lef[roots[i]], rig[roots[i]]);

    for (int i=0; i<n; ++i) que[i].clear();
    for (int i=0; i<2*n; ++i) dj[i].clear(), P[i]=i;
    for (int i=0; i<q; ++i) que[R[i]].pb(mp(E[i], i));
    uk=n, dt=0;

    for (int i=0; i<n; ++i) {
        dj[uk].pb(name(i));
        P[name(i)]=uk;
        for (int sus:ls[i]) {
            if (sus>=i || name(sus)==uk) continue;
            dj[uk].pb(name(sus));
            P[name(sus)]=uk;
        }
        uk++;
        for (pii pp:que[i]) roots[pp.Y]=name(pp.X);
    }
    dfs(name(0));
    for (int i=0; i<n; ++i) {
        p[i].Y=lef[i];
        toc[p[i].X].pb(p[i].Y);
    }
    for (int i=0; i<q; ++i) {
        r_y[i]=mp(lef[roots[i]], rig[roots[i]]);
        if (r_x[i].X) duz[r_x[i].X-1].pb(mp(r_y[i], mp(-1, i)));
        duz[r_x[i].Y].pb(mp(r_y[i], mp(1, i)));
    }
    sol.resize(q, 0);
    for (int i=0; i<2*n; ++i) {
        for (int y:toc[i]) update(y, 1);
        for (ppp pp:duz[i]) sol[pp.Y.Y]+=(query(pp.X.Y)-query(pp.X.X-1))*pp.Y.X;
    }
    for (int i=0; i<q; ++i) sol[i]=!!sol[i];
    return sol;
}

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