oj.uz

Submission #425925

# Submission time Handle Problem Language Result Execution time Memory
425925 2021-06-13T12:25:47 Z TryMax Werewolf (IOI18_werewolf) C++17
34 / 100
 1260 ms 524292 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 462 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 462 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1260 ms 91632 KB Output is correct
2 Correct 660 ms 91708 KB Output is correct
3 Correct 737 ms 91576 KB Output is correct
4 Correct 787 ms 91796 KB Output is correct
5 Correct 787 ms 91568 KB Output is correct
6 Correct 1120 ms 91908 KB Output is correct
7 Correct 1028 ms 90520 KB Output is correct
8 Correct 720 ms 91684 KB Output is correct
9 Correct 760 ms 89872 KB Output is correct
10 Correct 752 ms 90472 KB Output is correct
11 Correct 822 ms 91256 KB Output is correct
12 Correct 941 ms 91612 KB Output is correct
13 Correct 745 ms 91688 KB Output is correct
14 Correct 739 ms 91696 KB Output is correct
15 Correct 675 ms 91684 KB Output is correct
16 Correct 676 ms 91688 KB Output is correct
17 Correct 1081 ms 90328 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 462 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -