oj.uz

Submission #819713

# Submission time Handle Problem Language Result Execution time Memory
819713 2023-08-10T12:50:07 Z Trumling Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 21828 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

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) {
  int Q = S.size();
  ll m=X.size();

  vector<vector<int>>g(n);

  for(int i=0;i<m;i++)
  {
    g[X[i]].pb(Y[i]);
    g[Y[i]].pb(X[i]);
  }
  /*enter
  for(int i=0;i<n;i++)
  {
    for(auto r:g[i])
    cout<<r<<' ';
    enter
  }*/
 
  vector<int>ans;
  for(int i=0;i<Q;i++)
  {
    vector<vector<bool>>vis(2,vector<bool>(n,0));
    vis[0][S[i]]=1;

    set<int>q;
    q.insert(S[i]);
    while(!q.empty())
    {
      ll curr=*q.begin();
      q.erase(curr);
      if(curr<=R[i])
      vis[1][curr]=1;
     // cout<<curr<<',';
      for(auto r:g[curr])
      {
       // cout<<r<<' ';
        if(vis[0][curr] && !vis[0][r] &&  r>=L[i])
        {
          vis[0][r]=1;
          q.insert(r);
        }

        if(vis[1][curr] && !vis[1][r] && r<=R[i])
        {
          vis[1][r]=1;
          q.insert(r);
        }
      }
     // enter
    }
    //for(int i=0;i<n;i++)
  //  cout<<vis[0][i]<<' ';
   // enter
   // for(int i=0;i<n;i++)
   // cout<<vis[1][i]<<' ';
   // enter
   // enter
    ans.pb(vis[1][E[i]]);
  }
  return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 308 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 2 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 308 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 1008 ms 752 KB Output is correct
11 Correct 640 ms 732 KB Output is correct
12 Correct 20 ms 696 KB Output is correct
13 Correct 1145 ms 904 KB Output is correct
14 Correct 885 ms 760 KB Output is correct
15 Correct 499 ms 824 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 308 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 1008 ms 752 KB Output is correct
11 Correct 640 ms 732 KB Output is correct
12 Correct 20 ms 696 KB Output is correct
13 Correct 1145 ms 904 KB Output is correct
14 Correct 885 ms 760 KB Output is correct
15 Correct 499 ms 824 KB Output is correct
16 Execution timed out 4037 ms 21828 KB Time limit exceeded
17 Halted 0 ms 0 KB -