oj.uz

Submission #1013625

# Submission time Handle Problem Language Result Execution time Memory
1013625 2024-07-03T17:44:06 Z MarwenElarbi Werewolf (IOI18_werewolf) C++17
15 / 100
 1382 ms 19836 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=3e3+5;
vector<int> adj[nax];
vector<int> mn(nax);
vector<int> mx(nax);
bool vis[nax];
int n;
void min_djikastra(int x){
    priority_queue<int> pq;
    pq.push(x);
    mn[x]=x;
    vis[x]=true;
    while(!pq.empty()){
        int node=pq.top();
        pq.pop();
        for(auto u:adj[node]){
            if(vis[u]) continue;
            vis[u]=true;
            mn[u]=min(u,mn[node]);
            pq.push(u);
        }
    }
}
void max_djikastra(int x){
    priority_queue<int,vector<int>,greater<int>> pq;
    pq.push(x);
    mx[x]=x;
    vis[x]=true;
    while(!pq.empty()){
        int node=pq.top();
        pq.pop();
        for(auto u:adj[node]){
            if(vis[u]) continue;
            vis[u]=true;
            mx[u]=max(u,mx[node]);
            pq.push(u);
        }
    }
}
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) {
    n=N;
    for (int i = 0; i < (int)X.size(); ++i)
    {
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    vector<int> ans;
    int Q=R.size();
    for (int i = 0; i < Q; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            mn[j]=1e9;
            mx[j]=-1e9;
        }
        memset(vis,0,sizeof vis);
        min_djikastra(S[i]);
        memset(vis,0,sizeof vis);
        max_djikastra(E[i]);
        pair<int,int> cur={L[i],R[i]};
        bool test=false;
        for (int j = L[i]; j < R[i]+1; ++j)
        {
            if(cur.fi<=mn[j]&&mx[j]<=cur.se){
                test=true;
            }
            if(test) break;
        }//cout <<endl;
        ans.pb((test==true ? 1 : 0));
    }
    return ans;
}

/*namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}*/

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1176 ms 872 KB Output is correct
11 Correct 1027 ms 872 KB Output is correct
12 Correct 317 ms 876 KB Output is correct
13 Correct 1160 ms 888 KB Output is correct
14 Correct 939 ms 876 KB Output is correct
15 Correct 1382 ms 968 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 19836 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1176 ms 872 KB Output is correct
11 Correct 1027 ms 872 KB Output is correct
12 Correct 317 ms 876 KB Output is correct
13 Correct 1160 ms 888 KB Output is correct
14 Correct 939 ms 876 KB Output is correct
15 Correct 1382 ms 968 KB Output is correct
16 Runtime error 91 ms 19836 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -