Submission #425706

#	Time	Username	Problem	Language	Result	Execution time	Memory
425706		TryMax	Werewolf (IOI18_werewolf)	C++17	0 / 100	1373 ms	524292 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#ifdef LOCAL
    #include "grader.cpp"
#endif // LOCAL

#define f first
#define s second
#define pb push_back

using namespace std;

const int N = 2e5 + 10, inf = 1e9 + 10;

int canh[N], canw[N], pos[N], resg[N], resl[N];
vector<int> t[N], a;
vector<pair<int, pair<int, int>>> qg[N], ql[N];

void dfs(int u, int pr){
    a.pb(u);
    pos[u] = a.size() - 1;
    for(auto v : t[u])
        if(v != pr)
            dfs(v, u);
}

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<int> ans;
    ans.resize(q);
    for(int i = 0; i < m; ++i){
        t[x[i]].pb(y[i]);
        t[y[i]].pb(x[i]);
    }
    for(int i = 0; i < n; ++i)
        if(t[i].size() == 1){
            dfs(i, -1);
            break;
        }
    for(int i = 0; i < q; ++i){
        if(pos[s[i]] < pos[e[i]]){
            qg[r[i] + 1].pb({i, {1, pos[e[i]]}});
            ql[l[i] - 1].pb({i, {0, pos[s[i]]}});
        }else{
            qg[r[i] + 1].pb({i, {0, pos[e[i]]}});
            ql[l[i] - 1].pb({i, {1, pos[s[i]]}});
        }
    }
    set<int> st, st1;
    st.insert(inf);
    st1.insert(inf);
    for(int i = n - 1; i >= 0; --i){
        st.insert(pos[i]);
        st1.insert(-1 * pos[i]);
        for(auto v : qg[i]){
            if(v.s.f == 1)
                resg[v.f] = -1 * (*st1.upper_bound(-1 * v.s.s));
            else
                resg[v.f] = *st.upper_bound(v.s.s);
        }
    }
    st.clear();
    st1.clear();
    st.insert(inf);
    st1.insert(inf);
    for(int i = 0; i <= n - 1; ++i){
        st.insert(pos[i]);
        st1.insert(-1 * pos[i]);
        for(auto v : ql[i]){
            if(v.s.f == 1)
                resl[v.f] = -1 * (*st1.upper_bound(-1 * v.s.s));
            else
                resl[v.f] = *st.upper_bound(v.s.s);
        }
    }
    for(int i = 0; i < q; ++i){
        if(pos[s[i]] < pos[e[i]]){
            ans[i] = (resg[i] < resl[i]);
        }else
            ans[i] = (resg[i] > resl[i]);
    }
    return ans;
}
/*
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

6 5 1
3 4
4 2
2 0
0 1
1 5
3 1 3 1
*/

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