oj.uz

Submission #1018300

# Submission time Handle Problem Language Result Execution time Memory
1018300 2024-07-09T18:30:30 Z vjudge1 Werewolf (IOI18_werewolf) C++17
34 / 100
 516 ms 75144 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 max(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);
    menores.insert(-1);
    ffo(i,N){
        menores.erase(P[i]);
        for(auto qq : queries[i]){
            if(P[qq[1]] <= P[qq[2]]){
                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;
            }else{
                auto it = menores.upper_bound(P[qq[1]]);it--;
                int next_menor = *it;
                next_menor++;
                if(next_menor>P[qq[1]])continue;
                int l=P[qq[2]],r=P[qq[1]];
                while(l<=r){
                    int m=(l+r)/2;
                    if(query(P[qq[2]], m, sp) <= qq[0])l=m+1;
                    else r=m-1;
                }
                if(r>=next_menor)ans[qq[3]] = 1;
            }
        }
    }
    return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 73084 KB Output is correct
2 Correct 356 ms 75088 KB Output is correct
3 Correct 353 ms 74832 KB Output is correct
4 Correct 400 ms 74832 KB Output is correct
5 Correct 458 ms 75048 KB Output is correct
6 Correct 485 ms 74832 KB Output is correct
7 Correct 457 ms 73768 KB Output is correct
8 Correct 360 ms 75012 KB Output is correct
9 Correct 266 ms 73496 KB Output is correct
10 Correct 319 ms 75088 KB Output is correct
11 Correct 338 ms 75144 KB Output is correct
12 Correct 354 ms 74576 KB Output is correct
13 Correct 388 ms 75092 KB Output is correct
14 Correct 375 ms 74832 KB Output is correct
15 Correct 388 ms 74836 KB Output is correct
16 Correct 399 ms 75016 KB Output is correct
17 Correct 433 ms 73740 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -