oj.uz

답안 #1018224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018224 2024-07-09T16:50:53 Z vjudge1 늑대인간 (IOI18_werewolf) C++17
0 / 100
 494 ms 75024 KB 
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC target("popcnt")
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>
#define fls cout.flush()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using ii = pair<int,int>;
using mii = map<int,int>;
using lld = long double;
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
ll lcm(ll a, ll b){return (a/gcd(a,b))*b;}
const int LOG = 20;
int query(int l, int r, vector<vi>&sp){
    int lg = log2(r-l+1);
    return min(sp[l][lg], sp[r-(1<<lg)+1][lg]);
}
vi check_validity(int N, vi X, vi Y,vi S, vi E,vi L, vi R) {
    int Q = S.size(), M = sz(X);
    vi ans(Q,0), cn(N), P(N), A(N);
    vector<vi> graph(N);
    fo(i,M)cn[X[i]]++,cn[Y[i]]++,graph[X[i]].pb(Y[i]),graph[Y[i]].pb(X[i]);
    fo(i,N){
        if(cn[i]==1){
            P[i] = 0;
            int j = graph[i][0], p = i;
            int c=1;
            while(cn[j]==2){
                P[j]=c++;
                if(graph[j][0]==p)p=j,j=graph[j][1];
                else p=j,j=graph[j][0];
            }
            P[j]=c;
            break;
        }
    }
    fo(i,N)A[P[i]] = i;
    vector<vi> sp(N, vi(LOG, 0));
    fo(i,N)sp[i][0]=A[i];
    for(int bit = 1; bit < LOG; bit++){
        for(int i = 0;i<N-(1<<bit)+1; i++){
            sp[i][bit] = max(sp[i][bit-1] , sp[i+(1<<(bit-1))][bit-1]);
        }
    }
    vector<vector<array<int,4>>> queries(N);
    for (int i = 0; i < Q; ++i) {
        if(P[S[i]] > P[E[i]])swap(S[i], E[i]);
        queries[L[i]].pb({R[i], S[i], E[i], i});
    }
    set<int> menores;
    fo(i,N)menores.insert(P[i]);
    menores.insert(N);
    ffo(i,N){
        menores.erase(P[i]);
        for(auto qq : queries[i]){
            int next_menor=(*menores.lower_bound(P[qq[1]]));
            next_menor--;
            if(next_menor<P[qq[1]])continue;
            int l=P[qq[1]],r=P[qq[2]];
            while(l<=r){
                int m=(l+r)/2;
                if(query(m, P[qq[2]], sp) <= qq[0])r=m-1;
                else l=m+1;
            }
            if(l<=next_menor)ans[qq[3]] = 1;
        }
    }
    return ans;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 494 ms 75024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -