Submission #115680

#	Time	Username	Problem	Language	Result	Execution time	Memory
115680		someone_aa	Werewolf (IOI18_werewolf)	C++17	0 / 100	983 ms	70504 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
using namespace std;
const int maxn = 200100;
vector<int>g[maxn];
int n, m, q;
bool result[maxn];
// find path from x to y with l and r
class query{
public:
    int l, r, x, y, id;
};

vector<query>queries[maxn];

int uparent[maxn], usize[maxn];
int treeparent[maxn];

// DSU --->
int ufind(int x) {
    while(x != uparent[x])
        x = uparent[x];
    return x;
}
void unite(int x, int y) {
    x = ufind(x);
    y = ufind(y);

    if(usize[x] > usize[y]) {
        uparent[y] = x;
        usize[x] += usize[y];
    }
    else {
        uparent[x] = y;
        usize[y] += usize[x];
    }
}
bool connected(int x, int y) {
    return ufind(x) == ufind(y);
}
void init_dsu() {
    for(int i=0;i<n;i++) {
        uparent[i] = i;
        usize[i] = 1;
        treeparent[i] = i;
    }
}

// Tree's data
class tree {
public:
    vector<int>g[maxn];
    int st[maxn], sbtsize[maxn];
    int euler[maxn];
    int br = 0;

    bool check_subtree(int i, int x) {
        return st[i] >= st[x] && st[i] < st[x] + sbtsize[x];
    }
    void add_edge(int i, int j) {
        g[i].pb(j);
        g[j].pb(i);
    }
    void dfs(int node, int p) {
        st[node] = br;
        euler[br] = node;
        sbtsize[node] = 1;
        br++;

        for(int i:g[node]) {
            if(i != p) {
                dfs(i, node);
                sbtsize[node] += sbtsize[i];
            }
        }
    }
    void testdfs() {
        for(int i=0;i<n;i++) {
            cout<<i<<": "<<euler[i]<<" - "<<sbtsize[euler[i]]<<"\n";
        }
    }
}tpref, tsuff;

set<int>values;
void solve(int node, int p, bool keep = true) {
    int bigchild = -1;
    int maxv = 0;

    //cout<<node<<" - "<<keep<<"\n";

    for(int i:tsuff.g[node]) {
        if(i != p && tsuff.sbtsize[i] > maxv) {
            maxv = tsuff.sbtsize[i];
            bigchild = i;
        }
    }

    for(int i:tsuff.g[node]) {
        if(i != p && i != bigchild) {
            solve(i, node, false);
        }
    }

    if(bigchild != -1) {
        solve(bigchild, node, true);
    }

    for(int i:tsuff.g[node]) {
        if(i != p && i != bigchild) {
            for(int j=tsuff.st[i];j<tsuff.st[i]+tsuff.sbtsize[i];j++) {
                values.insert(tpref.st[tsuff.euler[j]]);
            }
        }
    }

    values.insert(tpref.st[node]);

    //cout<<node<<": \n";
    for(auto i:queries[node]) {
        //cout<<i.r<<" -> \n";
        auto x = values.lower_bound(tpref.st[i.r]);
        //cout<<(*x)<<"\n";

        if(x == values.end()) continue;
        if((*x) < tpref.st[i.r] + tpref.sbtsize[i.r]) result[i.id] = true;
    }

    /*cout<<node<<":\n";
    for(int i:values) {
        cout<<i<<" ";
    } cout<<"\n";*/

    if(!keep) {
        for(int j=tsuff.st[node];j<tsuff.st[node]+tsuff.sbtsize[node];j++) {
            values.erase(tpref.st[tsuff.euler[j]]);
        }
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    q = S.size(); n = N; m = X.size();
    for(int i=0;i<m;i++) {
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);
    }

    for(int i=0;i<q;i++) {
        queries[L[i]].pb({S[i], E[i], L[i], R[i], i});
    }

    init_dsu();
    for(int i=0;i<n;i++) {
        for(int j:g[i]) {
            if(i > j) {
                if(!connected(i, j)) {
                    tpref.add_edge(treeparent[ufind(i)], treeparent[ufind(j)]);
                    unite(i, j);
                    treeparent[ufind(i)] = i;
                }
            }
        }
    }

    init_dsu();
    for(int i=n-1;i>=0;i--) {
        for(int j:g[i]) {
            if(i < j) {
                if(!connected(i, j)) {
                    tsuff.add_edge(treeparent[ufind(i)], treeparent[ufind(j)]);
                    unite(i, j);
                    treeparent[ufind(i)] = i;
                }
            }
        }
    }

    tsuff.dfs(0, -1);
    tpref.dfs(n-1, -1);

    /*tsuff.testdfs();
    cout<<"---> NOW PREFIX: \n";
    tpref.testdfs();
    cout<<"---> NOW SOLVE: \n";*/
    solve(0, -1);

    vector<int> A(q);
    for (int i = 0; i < q; ++i) {
        A[i] = result[i] && tsuff.check_subtree(S[i], L[i]) && tpref.check_subtree(E[i], R[i]);
    }
    return A;
}

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