Submission #425925

#	Time	Username	Problem	Language	Result	Execution time	Memory
425925		TryMax	Werewolf (IOI18_werewolf)	C++17	34 / 100	1260 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 = 5e5 + 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]]}});
            if(l[i] >= 1)
                ql[l[i] - 1].pb({i, {0, pos[s[i]]}});
            resg[i] = -inf;
            resl[i] = inf;
        }else{
            qg[r[i] + 1].pb({i, {0, pos[e[i]]}});
            if(l[i] >= 1)
                ql[l[i] - 1].pb({i, {1, pos[s[i]]}});
            resg[i] = inf;
            resl[i] = -inf;
        }
    }
    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){
//        cout << pos[s[i]] << " " << pos[e[i]] << endl;
//        cout << resg[i] << " " << resl[i] << endl;
        if(pos[s[i]] < pos[e[i]]){
            ans[i] = (resg[i] < resl[i] - 1);
        }else
            ans[i] = (resg[i] - 1 > 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

10 9 1
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
9 4 5 6
*/

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