oj.uz

Submission #116235

# Submission time Handle Problem Language Result Execution time Memory
116235 2019-06-11T12:31:17 Z mirbek01 Werewolf (IOI18_werewolf) C++11
0 / 100
 4000 ms 29096 KB 
# include <bits/stdc++.h>
# include "werewolf.h"

using namespace std;

const int N = 4e5 + 2;

vector <int> g[N];

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
      int q = S.size();
      int m = X.size();
      vector <int> A(q);

      for(int i = 0; i < m; i ++){
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
      }

      for(int i = 0; i < q; i ++){
            queue <int> qe;
            vector <int> d(N, 0), used(N, 0);
            qe.push(S[i]);
            used[S[i]] = 1;
            d[S[i]] = 1;
            while(!qe.empty()){
                  int v = qe.front();
                  qe.pop();
                  for(int to : g[v]){
                        if(used[to] || to < L[i])
                              continue;
                        used[to] = 1;
                        d[to] ++;
                        qe.push(to);
                  }
            }
            for(int j = 0; j < N; j ++)
                  used[j] = 0;
            qe.push(E[i]);
            used[E[i]] = 1;
            d[E[i]] = 1;
            while(!qe.empty()){
                  int v = qe.front();
                  qe.pop();
                  for(int to : g[v]){
                        if(used[to] || to > R[i])
                              continue;
                        used[to] = 1;
                        d[to] ++;
                        qe.push(to);
                  }
            }
            for(int j = 0; j < N; j ++){
                  if(d[j] == 2)
                        A[i] = 1;
            }
      }

      return A;
}
/***
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
****/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9728 KB Output is correct
2 Incorrect 10 ms 9648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9728 KB Output is correct
2 Incorrect 10 ms 9648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4089 ms 29096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9728 KB Output is correct
2 Incorrect 10 ms 9648 KB Output isn't correct
3 Halted 0 ms 0 KB -