oj.uz

답안 #770296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
770296 2023-07-01T05:11:04 Z boyliguanhan 늑대인간 (IOI18_werewolf) C++17
0 / 100
 4000 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],n;
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;
    n=N;
    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:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<X.size();i++)
      |                 ~^~~~~~~~~
werewolf.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 309 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 309 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4077 ms 70384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 309 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -