oj.uz

답안 #778001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778001 2023-07-10T02:06:28 Z Magikarp4000 늑대인간 (IOI18_werewolf) C++17
34 / 100
 1693 ms 524288 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 solve(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;
        // cout << "sv ev: " << sv << " " << ev << ln;
        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;
        // cout << "sv ev: " << sv << " " << ev << ln;
        return sv <= ev;
    }
}

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]);
    }
    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 = solve(S[i],E[i],L[i],R[i]);
        res.PB(ans);
    }
    return res;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 263 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 263 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1495 ms 33436 KB Output is correct
2 Correct 1670 ms 41664 KB Output is correct
3 Correct 1693 ms 41708 KB Output is correct
4 Correct 1674 ms 41744 KB Output is correct
5 Correct 1646 ms 41752 KB Output is correct
6 Correct 1512 ms 41688 KB Output is correct
7 Correct 1590 ms 41900 KB Output is correct
8 Correct 1650 ms 41812 KB Output is correct
9 Correct 977 ms 41684 KB Output is correct
10 Correct 1262 ms 41808 KB Output is correct
11 Correct 1288 ms 41732 KB Output is correct
12 Correct 1246 ms 41780 KB Output is correct
13 Correct 1620 ms 41668 KB Output is correct
14 Correct 1668 ms 41736 KB Output is correct
15 Correct 1690 ms 41756 KB Output is correct
16 Correct 1657 ms 41868 KB Output is correct
17 Correct 1666 ms 41888 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 263 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -