oj.uz

답안 #569512

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
569512 2022-05-27T12:50:44 Z NemanjaSo2005 늑대인간 (IOI18_werewolf) C++14
0 / 100
 4000 ms 39252 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,Q,prosli[200005],pos[200005],pvred;
vector<int> graf[200005],ret;
struct kveri{
   int poc,kraj,id;
   ll L,R;
} upiti[200005];
void dfs(int gde,int L,int R){
  // cout<<"DFS sa "<<pvred<<" u "<<gde<<endl;
   prosli[gde]=pvred;
   pos[gde]++;
   for(int i=0;i<graf[gde].size();i++){
      if(prosli[graf[gde][i]]==pvred)
         continue;
      //cout<<graf[gde][i]<<" "<<L<<" "<<R<<endl;
      if(graf[gde][i]<L)
         continue;
      if(graf[gde][i]>R)
         continue;
     // cout<<"DALJE"<<endl;
      dfs(graf[gde][i],L,R);
   }
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
   N=NN;
   M=X.size();
   Q=L.size();
   ret.resize(Q);
   for(int i=0;i<M;i++){
      X[i]++;
      Y[i]++;
      graf[X[i]].push_back(Y[i]);
      graf[Y[i]].push_back(X[i]);
   }
   for(int i=0;i<Q;i++){
      S[i]++;
      E[i]++;
      L[i]++;
      R[i]++;
      upiti[i+1].id=i;
      upiti[i+1].poc=S[i];
      upiti[i+1].kraj=E[i];
      upiti[i+1].L=R[i];
      upiti[i+1].R=L[i];
   }
   if(N*Q<=10000000){
      for(int j=1;j<=Q;j++){
         for(int i=1;i<=N;i++)
            pos[i]=0;
         pvred++;
         dfs(upiti[j].poc,upiti[j].L,N);
        // for(int i=1;i<=N;i++)
         //   cout<<pos[i]<<" ";
         //cout<<endl;
         pvred++;
         dfs(upiti[j].kraj,1,upiti[j].R);
         //for(int i=1;i<=N;i++)
          //  cout<<pos[i]<<" ";
         //cout<<endl;
         ret[upiti[j].id]=0;
         for(int i=1;i<=N;i++)
            if(pos[i]==2)
               ret[upiti[j].id]=1;
      }
      return ret;
   }
}

Compilation message

werewolf.cpp: In function 'void dfs(int, int, int)':
werewolf.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |    for(int i=0;i<graf[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~
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:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -