oj.uz

Submission #778002

# Submission time Handle Problem Language Result Execution time Memory
778002 2023-07-10T02:10:50 Z Magikarp4000 Werewolf (IOI18_werewolf) C++17
49 / 100
 1692 ms 36592 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

struct Node {
    int mi,ma;
};

const int MAXN = 2e5+5;
vector<int> v[MAXN];
int n,m,Q;
int start;
bool z[MAXN], z1[MAXN];
int pos[MAXN];
Node st[MAXN*4+10];

void dfs(int s, int pa) {
    FORX(u,v[s]) {
        if (u == pa) continue;
        pos[u] = pos[s]+1;
        dfs(u,s);
    }
}

void update(int s, int tl, int tr, int idx, int val) {
    if (tl == tr) st[s].mi = st[s].ma = val;
    else {
        int tm = (tl+tr)/2;
        if (idx <= tm) update(s*2,tl,tm,idx,val);
        else update(s*2+1,tm+1,tr,idx,val);
        st[s].mi = min(st[s*2].mi, st[s*2+1].mi);
        st[s].ma = max(st[s*2].ma, st[s*2+1].ma);
    }
}

int query(int s, int tl, int tr, int l, int r, int tp) {
    if (l <= tl && r >= tr) return tp == 0 ? st[s].mi : st[s].ma;
    else {
        int tm = (tl+tr)/2;
        int cur = tp == 0 ? INF : -INF;
        if (l <= tm) cur = query(s*2,tl,tm,l,r,tp);
        if (r > tm) {
            if (tp == 0) cur = min(cur, query(s*2+1,tm+1,tr,l,r,tp));
            else cur = max(cur, query(s*2+1,tm+1,tr,l,r,tp));
        }
        return cur;
    }
}

bool solve3(int sta, int en, int lt, int rt) {
    if (pos[sta] < pos[en]) {
        int l = pos[sta], r = n-1;
        while (l < r) {
            int mid = (l+r+1)/2;
            int check = query(1,0,n-1,pos[sta],mid,0);
            if (check < lt) r = mid-1;
            else l = mid;
        }
        int sv = l;
        l = 0, r = pos[en];
        while (l < r) {
            int mid = (l+r)/2;
            int check = query(1,0,n-1,mid,pos[en],1);
            if (check > rt) l = mid+1;
            else r = mid;
        }
        int ev = l;
        return sv >= ev;
    }
    else {
        int l = 0, r = pos[sta];
        while (l < r) {
            int mid = (l+r)/2;
            int check = query(1,0,n-1,mid,pos[sta],0);
            if (check < lt) l = mid+1;
            else r = mid;
        }
        int sv = l;
        l = pos[en], r = n-1;
        while (l < r) {
            int mid = (l+r+1)/2;
            int check = query(1,0,n-1,pos[en],mid,1);
            if (check > rt) r = mid-1;
            else l = mid;
        }
        int ev = l;
        return sv <= ev;
    }
}

void reset() {
    FOR(i,0,n) {
        z[i] = z1[i] = 0;
    }
}

bool solve2(int sta, int en, int l, int r) {
    queue<int> q;
    q.push(sta);
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        z[s] = 1;
        FORX(u,v[s]) {
            if (z[u] || u < l) continue;
            q.push(u);
        }
    }
    q.push(en);
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        z1[s] = 1;
        FORX(u,v[s]) {
            if (z1[u] || u > r) continue;
            q.push(u);
        }
    }
    FOR(i,0,n) if (z[i] && z1[i]) return 1;
    return 0;
}

vector<int> sub2(vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    vector<int> res;
    FOR(i,0,Q) {
        reset();
        bool ans = solve2(S[i],E[i],L[i],R[i]);
        res.PB(ans);
    }
    return res;
}

vector<int> sub3(vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    FOR(i,0,n) if (v[i].size() == 1) start = i;
    dfs(start,-1);
    FOR(i,0,n) update(1,0,n-1,pos[i],i);
    vector<int> res;
    FOR(i,0,Q) {
        bool ans = solve3(S[i],E[i],L[i],R[i]);
        res.PB(ans);
    }
    return res;
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    n = N, m = X.size(), Q = S.size();
    FOR(i,0,m) {
        v[X[i]].PB(Y[i]);
        v[Y[i]].PB(X[i]);
    }
    if (n <= 3000 && m <= 6000 && Q <= 3000) return sub2(S,E,L,R);
    return sub3(S,E,L,R);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5012 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5012 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 306 ms 5532 KB Output is correct
11 Correct 93 ms 5404 KB Output is correct
12 Correct 15 ms 5436 KB Output is correct
13 Correct 315 ms 5432 KB Output is correct
14 Correct 117 ms 5404 KB Output is correct
15 Correct 504 ms 5536 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1456 ms 36484 KB Output is correct
2 Correct 1692 ms 36440 KB Output is correct
3 Correct 1676 ms 36464 KB Output is correct
4 Correct 1645 ms 36572 KB Output is correct
5 Correct 1654 ms 36384 KB Output is correct
6 Correct 1603 ms 36428 KB Output is correct
7 Correct 1616 ms 36444 KB Output is correct
8 Correct 1633 ms 36472 KB Output is correct
9 Correct 966 ms 36548 KB Output is correct
10 Correct 1225 ms 36416 KB Output is correct
11 Correct 1281 ms 36492 KB Output is correct
12 Correct 1262 ms 36468 KB Output is correct
13 Correct 1667 ms 36488 KB Output is correct
14 Correct 1665 ms 36592 KB Output is correct
15 Correct 1684 ms 36544 KB Output is correct
16 Correct 1672 ms 36460 KB Output is correct
17 Correct 1626 ms 36456 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5012 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 306 ms 5532 KB Output is correct
11 Correct 93 ms 5404 KB Output is correct
12 Correct 15 ms 5436 KB Output is correct
13 Correct 315 ms 5432 KB Output is correct
14 Correct 117 ms 5404 KB Output is correct
15 Correct 504 ms 5536 KB Output is correct
16 Correct 1456 ms 36484 KB Output is correct
17 Correct 1692 ms 36440 KB Output is correct
18 Correct 1676 ms 36464 KB Output is correct
19 Correct 1645 ms 36572 KB Output is correct
20 Correct 1654 ms 36384 KB Output is correct
21 Correct 1603 ms 36428 KB Output is correct
22 Correct 1616 ms 36444 KB Output is correct
23 Correct 1633 ms 36472 KB Output is correct
24 Correct 966 ms 36548 KB Output is correct
25 Correct 1225 ms 36416 KB Output is correct
26 Correct 1281 ms 36492 KB Output is correct
27 Correct 1262 ms 36468 KB Output is correct
28 Correct 1667 ms 36488 KB Output is correct
29 Correct 1665 ms 36592 KB Output is correct
30 Correct 1684 ms 36544 KB Output is correct
31 Correct 1672 ms 36460 KB Output is correct
32 Correct 1626 ms 36456 KB Output is correct
33 Incorrect 679 ms 34576 KB Output isn't correct
34 Halted 0 ms 0 KB -