oj.uz

Submission #1039385

# Submission time Handle Problem Language Result Execution time Memory
1039385 2024-07-30T19:38:19 Z vnm06 Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 52752 KB 
#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

int q, n, m;
vector<int> gr[400005];
bool dost[400005][2];

void dfs(int v, int ty, int Le, int Ri)
{
    dost[v][ty]=1;
    if(ty==0 && v<=Ri && !dost[v][1]) dfs(v, 1, Le, Ri);
    int brs=gr[v].size();
    for(int i=0; i<brs; i++)
    {
        int nv=gr[v][i];
        if(dost[nv][ty]) continue;
        if(nv<=Ri && ty==1) dfs(nv, ty, Le, Ri);
        if(nv>=Le && ty==0) dfs(nv, ty, Le, Ri);
    }
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) 
{
  q=S.size();
  n=N;
  m=X.size();
  for(int i=0; i<m; i++)
  {
    gr[X[i]].push_back(Y[i]);
    gr[Y[i]].push_back(X[i]);
  }

    vector<int> A;
  A.resize(q);
  for(int i=0; i<q; i++) 
  {
    memset(dost, 0, sizeof(dost));
    dfs(S[i], 0, L[i], R[i]);
    A[i]=dost[E[i]][1];
  }
  return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 10588 KB Output is correct
3 Correct 4 ms 10628 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10624 KB Output is correct
7 Correct 4 ms 10436 KB Output is correct
8 Correct 4 ms 10588 KB Output is correct
9 Correct 4 ms 10588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 10588 KB Output is correct
3 Correct 4 ms 10628 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10624 KB Output is correct
7 Correct 4 ms 10436 KB Output is correct
8 Correct 4 ms 10588 KB Output is correct
9 Correct 4 ms 10588 KB Output is correct
10 Correct 286 ms 11016 KB Output is correct
11 Correct 171 ms 10940 KB Output is correct
12 Correct 59 ms 11228 KB Output is correct
13 Correct 264 ms 11212 KB Output is correct
14 Correct 157 ms 10840 KB Output is correct
15 Correct 254 ms 11208 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 4 ms 10588 KB Output is correct
3 Correct 4 ms 10628 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10624 KB Output is correct
7 Correct 4 ms 10436 KB Output is correct
8 Correct 4 ms 10588 KB Output is correct
9 Correct 4 ms 10588 KB Output is correct
10 Correct 286 ms 11016 KB Output is correct
11 Correct 171 ms 10940 KB Output is correct
12 Correct 59 ms 11228 KB Output is correct
13 Correct 264 ms 11212 KB Output is correct
14 Correct 157 ms 10840 KB Output is correct
15 Correct 254 ms 11208 KB Output is correct
16 Execution timed out 4067 ms 52752 KB Time limit exceeded
17 Halted 0 ms 0 KB -