oj.uz

Submission #1111634

# Submission time Handle Problem Language Result Execution time Memory
1111634 2024-11-12T12:19:35 Z SalihSahin Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 48920 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "werewolf.h"
 
vector<int> par;
vector<vector<int> > adj1, adj2, adj;
 
int fnd(int a){
  if(a == par[a]) return a;
  return par[a] = fnd(par[a]);
}
 
bool merge(int a, int b, int g){
  a = fnd(a), b = fnd(b);
  if(a == b) return 0;
 
  if(g == 0){
    adj1[a].pb(b);
    adj1[b].pb(a);
    par[min(a, b)] = max(a, b);
  }
  else{
    adj2[a].pb(b);
    adj2[b].pb(a);
    par[max(a, b)] = min(a, b);
  }
 
  return 1;
}
 
vector<int> in1, out1, in2, out2, p1, p2;
int timer;
 
void dfs1(int node, int par){
  in1[node] = ++timer;
  p1[node] = par;
  for(auto itr: adj1[node]){
    if(itr == par) continue;
    dfs1(itr, node);
  }
  out1[node] = timer;
}
 
void dfs2(int node, int par){
  in2[node] = ++timer;
  p2[node] = par;
  for(auto itr: adj2[node]){
    if(itr == par) continue;
    dfs2(itr, node);
  }
  out2[node] = timer;
}
 
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();
  adj1.resize(N);
  adj2.resize(N);
  adj.resize(N);
  par.resize(N);
  in1.resize(N);
  in2.resize(N);
  out1.resize(N);
  out2.resize(N);
  p1.resize(N);
  p2.resize(N);
 
  for(int i = 0; i < m; i++){
    adj[X[i]].pb(Y[i]);
    adj[Y[i]].pb(X[i]);
  }
  for(int i = 0; i < N; i++){
    par[i] = i;
  }
 
  for(int i = 0; i < N; i++){
    for(auto itr: adj[i]){
      if(itr > i) continue;
      merge(i, itr, 0);
    }
  } // adj1'i oluşturuyoruz -> werewolf path
 
  for(int i = 0; i < N; i++){
    par[i] = i;
  }
 
  for(int i = N-1; i >= 0; i--){
    for(auto itr: adj[i]){
      if(itr < i) continue;
      merge(i, itr, 1);
    }
  } // adj2'yi oluşturuyoruz -> human path
  timer = 0;
  dfs1(N-1, N-1);
  timer = 0;
  dfs2(0, 0);
  /*
  for(int i = 0; i < N; i++){
    cout<<i<<" -> "<<in1[i]<<" "<<out1[i]<<" ve 2. agac "<<in2[i]<<" "<<out2[i]<<endl;
  }*/
 
  vector<int> ans(q);
  for (int i = 0; i < q; ++i) {
    int start = S[i], finish = E[i];
    while(start != 0 && p2[start] >= L[i]) start = p2[start];
    while(finish != N-1 && p1[finish] <= R[i]) finish = p1[finish];
    //cout<<i<<" "<<start<<" "<<finish<<endl;
 
    bool ortak = 0;
    for(int j = L[i]; j <= R[i]; j++){
      bool anc2 = (in2[start] <= in2[j] && out2[start] >= out2[j]);
      bool anc1 = (in1[finish] <= in1[j] && out1[finish] >= out1[j]);
      if(anc1 && anc2){
        ortak = true;
        //cout<<i<<" -> "<<j<<" ok "<<endl;
      }
    }
 
    if(ortak) ans[i] = 1;
  }
  return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 18 ms 1104 KB Output is correct
11 Correct 22 ms 1104 KB Output is correct
12 Correct 22 ms 1104 KB Output is correct
13 Correct 22 ms 1104 KB Output is correct
14 Correct 21 ms 1308 KB Output is correct
15 Correct 23 ms 1104 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 18 ms 1104 KB Output is correct
11 Correct 22 ms 1104 KB Output is correct
12 Correct 22 ms 1104 KB Output is correct
13 Correct 22 ms 1104 KB Output is correct
14 Correct 21 ms 1308 KB Output is correct
15 Correct 23 ms 1104 KB Output is correct
16 Execution timed out 4065 ms 48920 KB Time limit exceeded
17 Halted 0 ms 0 KB -