oj.uz

Submission #770305

# Submission time Handle Problem Language Result Execution time Memory
770305 2023-07-01T05:22:30 Z boyliguanhan Werewolf (IOI18_werewolf) C++17
34 / 100
 1018 ms 524288 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[400100];
int lg[400100],tb[400100][21],pos[400100],tb2[400100][21];
vector<int>temp;
void dfs(int n,int p){
    pos[n]=temp.size(),temp.push_back(n);
    for(auto i: adj[n])
        if(i!=p)
            dfs(i,n);
}
int querymin(int l,int r){
    return min(tb[l][lg[r-l+1]],tb[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
int querymax(int l,int r){
    return max(tb2[l][lg[r-l+1]],tb2[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
bool calc(int s,int e,int l,int r){
    int pos1=pos[s],pos2=pos[e],rev=0;
    if(pos1>pos2)
        swap(pos1,pos2),rev=1;
    int L=pos1,R=pos2,best=pos1;
    while(L<=R){
        int mid = L+R>>1;
        if((querymin(pos1,mid)>=l&&!rev)||(querymax(pos1,mid)<=r&&rev))
            L=mid+1,best=max(mid,best);
        else
            R=mid-1;
    }
    return (querymax(best,pos2)<=r&&!rev)||(querymin(best,pos2)>=l&&rev);
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>s,vector<int>e,vector<int>l,vector<int>r){
    lg[1]=0;
    vector<int> ans;
    for(int i=2;i<200100;i++)
        lg[i]=lg[i/2]+1;
    for(int i=0;i<X.size();i++)
        adj[X[i]].push_back(Y[i]),adj[Y[i]].push_back(X[i]);
    for(int i=0;i<N;i++)
        if(adj[i].size()==1){
        dfs(i,N);
        break;
    }
    for(int i=0;i<N;i++)
        tb[i][0]=temp[i],tb2[i][0]=temp[i];
    for(int l=1;l<21;l++){
        for(int i=0;i+(1<<l)<=N;i++){
            tb[i][l]=min(tb[i][l-1],tb[i+(1<<(l-1))][l-1]);
            tb2[i][l]=max(tb2[i][l-1],tb2[i+(1<<(l-1))][l-1]);
        }
    }
    for(int i=0;i<s.size();i++){
        ans.push_back(calc(s[i],e[i],l[i],r[i]));
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'bool calc(int, int, int, int)':
werewolf.cpp:25:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         int mid = L+R>>1;
      |                   ~^~
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:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<X.size();i++)
      |                 ~^~~~~~~~~
werewolf.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1018 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 1018 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 396 ms 79872 KB Output is correct
2 Correct 372 ms 79908 KB Output is correct
3 Correct 382 ms 80080 KB Output is correct
4 Correct 396 ms 79860 KB Output is correct
5 Correct 417 ms 79920 KB Output is correct
6 Correct 417 ms 80060 KB Output is correct
7 Correct 395 ms 79896 KB Output is correct
8 Correct 340 ms 79888 KB Output is correct
9 Correct 238 ms 80012 KB Output is correct
10 Correct 231 ms 79936 KB Output is correct
11 Correct 227 ms 79960 KB Output is correct
12 Correct 241 ms 79924 KB Output is correct
13 Correct 366 ms 79980 KB Output is correct
14 Correct 413 ms 79924 KB Output is correct
15 Correct 344 ms 79944 KB Output is correct
16 Correct 369 ms 79932 KB Output is correct
17 Correct 343 ms 79924 KB Output is correct

Subtask #4
0 / 51.0

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