oj.uz

Submission #770306

# Submission time Handle Problem Language Result Execution time Memory
770306 2023-07-01T05:23:21 Z vjudge1 Werewolf (IOI18_werewolf) C++17
34 / 100
 1105 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 1105 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 1105 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 374 ms 73684 KB Output is correct
2 Correct 394 ms 73692 KB Output is correct
3 Correct 408 ms 73684 KB Output is correct
4 Correct 411 ms 73660 KB Output is correct
5 Correct 414 ms 73624 KB Output is correct
6 Correct 400 ms 73592 KB Output is correct
7 Correct 431 ms 73588 KB Output is correct
8 Correct 351 ms 73668 KB Output is correct
9 Correct 272 ms 73700 KB Output is correct
10 Correct 235 ms 73672 KB Output is correct
11 Correct 257 ms 73592 KB Output is correct
12 Correct 287 ms 73636 KB Output is correct
13 Correct 440 ms 73624 KB Output is correct
14 Correct 414 ms 73624 KB Output is correct
15 Correct 424 ms 73680 KB Output is correct
16 Correct 400 ms 73672 KB Output is correct
17 Correct 393 ms 73696 KB Output is correct

Subtask #4
0 / 51.0

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