oj.uz

Submission #772224

# Submission time Handle Problem Language Result Execution time Memory
772224 2023-07-03T18:30:00 Z I_Love_EliskaM_ Werewolf (IOI18_werewolf) C++14
15 / 100
 282 ms 13200 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

vector<int> p1(int n, vector<int>x, vector<int>y, vector<int>s, vector<int>e, vector<int>L, vector<int>R) {
  int m=x.size(), Q=L.size();
  vector<int> ok(n,0), vis(n,0);
  vector<vector<int>> adj(n);
  forn(i,m) {
    int u=x[i], v=y[i];
    adj[u].pb(v); adj[v].pb(u);
  }
  vector<int> ans(Q);
  forn(it,Q) {
    int l=L[it], r=R[it];
    queue<int> q; q.push(s[it]);
    while (q.size()) {
      auto u=q.front(); q.pop();
      if (u<l) continue;
      if (vis[u]) continue;
      vis[u]=1;
      if (l<=u && u<=r) ok[u]=1;
      for(auto&v:adj[u]) q.push(v);
    }
    forn(i,n) vis[i]=0;
    forn(i,n) if (ok[i]) q.push(i);
    while (q.size()) {
      auto u=q.front(); q.pop();
      if (u>r) continue;
      if (vis[u]) continue;
      vis[u]=1;
      for(auto&v:adj[u]) q.push(v);
    }
    ans[it]=vis[e[it]];
    forn(i,n) vis[i]=ok[i]=0;
  }
  return ans;
}

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 m=x.size(), q=l.size();
    if (max(m,q)<=6000) {
        return p1(n,x,y,s,e,l,r);
    }
    return vector<int>(q,0);
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 282 ms 860 KB Output is correct
11 Correct 203 ms 820 KB Output is correct
12 Correct 33 ms 724 KB Output is correct
13 Correct 252 ms 836 KB Output is correct
14 Correct 180 ms 816 KB Output is correct
15 Correct 201 ms 952 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 13200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 282 ms 860 KB Output is correct
11 Correct 203 ms 820 KB Output is correct
12 Correct 33 ms 724 KB Output is correct
13 Correct 252 ms 836 KB Output is correct
14 Correct 180 ms 816 KB Output is correct
15 Correct 201 ms 952 KB Output is correct
16 Incorrect 111 ms 13200 KB Output isn't correct
17 Halted 0 ms 0 KB -