oj.uz

Submission #999170

# Submission time Handle Problem Language Result Execution time Memory
999170 2024-06-15T07:47:56 Z Unforgettablepl Werewolf (IOI18_werewolf) C++17
34 / 100
 389 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()

struct segtree{
    vector<int> tree;
    segtree():tree(524288,200000){}
    void update(int k,int x){
        k+=262144;
        tree[k]=x;
        k/=2;
        while(k){
            tree[k]=min(tree[2*k],tree[2*k+1]);
            k/=2;
        }
    }
    int get(int L,int R){
        L+=262144;R+=262144;
        int ans = 200000;
        while(L<=R){
            if(L&1)ans=min(ans,tree[L++]);
            if(R%2==0)ans=min(ans,tree[R--]);
            L/=2;R/=2;
        }
        return ans;
    }
};


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) {
    int n = N;
    vector<vector<int>> adj(n);
    for(int i=0;i<X.size();i++){
        adj[X[i]].emplace_back(Y[i]);
        adj[Y[i]].emplace_back(X[i]);
    }
    vector<int> idx(n);
    int uid = 0;
    function<void (int,int)> dfs = [&](int x,int p){
        idx[x] = uid++;
        for(int&i:adj[x])if(i!=p)dfs(i,x);
    };
    for(int i=0;i<n;i++)if(adj[i].size()==1){dfs(i,-1);break;}
    segtree seg;
    segtree segmax;
    for(int i=0;i<n;i++)seg.update(idx[i],i);
    for(int i=0;i<n;i++)segmax.update(idx[i],-i);
    vector<int> ans(S.size());
    for(int i=0;i<S.size();i++){
        int s = idx[S[i]];
        int e = idx[E[i]];
        if(seg.get(s,s)<L[i])continue;
        if(s<e){
            int base = s;
            for(int jump=131072;jump;jump/=2){
                if(base+jump>e)continue;
                if(seg.get(s,base+jump)>=L[i])base+=jump;
            }
            if(-segmax.get(base,e)<=R[i])ans[i]=1;
        } else {
            int base = s;
            for(int jump=131072;jump;jump/=2){
                if(base-jump<e)continue;
                if(seg.get(base-jump,s)>=L[i])base-=jump;
            }
            if(-segmax.get(e,base)<=R[i])ans[i]=1;
        }
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<X.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 524288 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 276 ms 524288 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 303 ms 50512 KB Output is correct
2 Correct 340 ms 50548 KB Output is correct
3 Correct 333 ms 50444 KB Output is correct
4 Correct 354 ms 50512 KB Output is correct
5 Correct 359 ms 50452 KB Output is correct
6 Correct 335 ms 50516 KB Output is correct
7 Correct 385 ms 50552 KB Output is correct
8 Correct 347 ms 50512 KB Output is correct
9 Correct 201 ms 50324 KB Output is correct
10 Correct 259 ms 50304 KB Output is correct
11 Correct 264 ms 50512 KB Output is correct
12 Correct 216 ms 50512 KB Output is correct
13 Correct 367 ms 50432 KB Output is correct
14 Correct 366 ms 50516 KB Output is correct
15 Correct 364 ms 50308 KB Output is correct
16 Correct 370 ms 50768 KB Output is correct
17 Correct 389 ms 50516 KB Output is correct

Subtask #4
0 / 51.0

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