oj.uz

Submission #796833

# Submission time Handle Problem Language Result Execution time Memory
796833 2023-07-28T19:31:12 Z anton Amusement Park (JOI17_amusement_park) C++17
28 / 100
 19 ms 5488 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;

static const int MAX_N = 1e4;
static const int K = 60;
static int x[K];
static bool vis[MAX_N];
static vector<int> order;
static vector<int> adj[MAX_N];

void dfs(int u, int a){
  MessageBoard(u, x[order.size()%K]);
  //cout<<u<<endl;
  order.push_back(u);
  vis[u] = true;

  for(auto v: adj[u]){
    if(!vis[v]){
      dfs(v, u);
    }
  }
  //cout<<u<<endl;
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
  for(long long i = 0; i<K; i++){
    if((X&(1LL<<i))>0LL){
      x[i] = 1;
    }
    else{
      x[i] = 0;
    }
    //cout<<x[i]<<" ";
  }

  for(int i = 0; i<M; i++){
    int a, b;
    a = A[i];
    b =B[i];
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  dfs(0, -1);
}

#include "Ioi.h"
#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 1e4;
const int K = 60;
static int x2[K], mod[MAX_N], anc[MAX_N], sz[MAX_N], place[MAX_N], among_peers[MAX_N];
static bool vis2[MAX_N], found[K];
static int nb_vis =0;
static vector<int> order2;
static vector<int> adj2[MAX_N];
static vector<int> ch[MAX_N];

void dfs2(int u, int a){
  vis2[u] = true;
  anc[u] =a;
  mod[u] = nb_vis;
  place[u] = order2.size();
  nb_vis++;
  ////cout<<u<<" "<<mod[u]<<endl;
  order2.push_back(u);
  sz[u] =1;

  for(auto v: adj2[u]){
    if(!vis2[v]){
      among_peers[v] = ch[u].size();
      ch[u].push_back(v);
      dfs2(v, u);
      sz[u] += sz[v];
      order2.push_back(u);
    }
  }

}
int nb_found = 0;

void find(int id, int v){
  if(!found[id]){
    found[id] = true;
    nb_found++;
    x2[id] = v;
  }
}

void explore_after(int u, int order){
  //cout<<"exploring "<<u<<" after "<<order<<endl;
  //cout<<mod[u]<<endl;
  for(int i = order; i<ch[u].size() && nb_found<K; i++){
    int next = ch[u][i];
    int val = Move(next);
    find(mod[next]%K, val);
    explore_after(next, 0);
    if(nb_found<K){
      Move(u);
    }
  }
  //cout<<"done "<<u<<endl;
}

void explore_before(int u, int order){
  //cout<<"exploring "<<u<<" before "<<order<<endl;
  //cout<<mod[u]<<endl;
  for(int i = order; i>=0 && nb_found<K; i--){
    int next = ch[u][i];
    int val = Move(next);
    find(mod[next]%K, val);
    explore_before(next, ch[next].size()-1);
    if(nb_found<K){
      Move(u);
    }
  }
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {

  for(int i = 0; i<M; i++){
    int a, b;
    a = A[i];
    b =B[i];
    adj2[a].push_back(b);
    adj2[b].push_back(a);
  }

  dfs2(0, -1);

  int cur = P;
  find(mod[cur]%K, V);
  for(int i= 0; i< order2.size(); i++){
    ////cout<<i<<" "<<order2[i]<<" | ";
  }
  ////cout<<endl;

  explore_after(cur, 0);
  //explore_before(cur, ch[cur].size()-1);
  while(nb_found<K){
    ////cout<<anc[cur]<<endl;
    int val =Move(anc[cur]);
    
    find(mod[anc[cur]]%K, val);
    explore_after(anc[cur], among_peers[cur]+1);
    explore_before(anc[cur], among_peers[cur]-1);

    //explore_before(anc[cur], among_peers[cur]-1);
    cur = anc[cur];
  }

  /*////cout<<"done going up "<<cur<<" "<<endl;
  int pos = place[cur]+1;
  ////cout<<"first at "<<pos<<endl;
  for(int i = pos; nb_found<K; i++){
    ////cout<<"going to "<<order2[i]<<endl;
    int val =Move(order2[i]);
    cur= order2[i];
    find(mod[cur]%K, val); 
  }*/

  long long res= 0;
  for(long long i = 0; i<K; i++){
    if(x2[i]){
      res+=(1LL<<i);
    }
  }

  ////cout<<res<<endl;
  return res;
}

Compilation message

Ioi.cpp: In function 'void explore_after(int, int)':
Ioi.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i = order; i<ch[u].size() && nb_found<K; i++){
      |                      ~^~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int i= 0; i< order2.size(); i++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 1 ms 1360 KB Output is correct
3 Correct 2 ms 1296 KB Output is correct
4 Correct 1 ms 1284 KB Output is correct
5 Correct 1 ms 1264 KB Output is correct
6 Correct 1 ms 1284 KB Output is correct
7 Correct 2 ms 1372 KB Output is correct
8 Correct 2 ms 1368 KB Output is correct
9 Correct 1 ms 1288 KB Output is correct
10 Correct 1 ms 1284 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 1 ms 1284 KB Output is correct
13 Correct 2 ms 1292 KB Output is correct
14 Correct 2 ms 1288 KB Output is correct
15 Correct 1 ms 1288 KB Output is correct
16 Correct 2 ms 1288 KB Output is correct
17 Correct 2 ms 1288 KB Output is correct
18 Correct 2 ms 1288 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5064 KB Output is correct
2 Correct 17 ms 5068 KB Output is correct
3 Correct 17 ms 5072 KB Output is correct
4 Correct 10 ms 3396 KB Output is correct
5 Correct 11 ms 4164 KB Output is correct
6 Correct 10 ms 3776 KB Output is correct
7 Correct 11 ms 3908 KB Output is correct
8 Correct 10 ms 3944 KB Output is correct
9 Correct 11 ms 3936 KB Output is correct
10 Correct 9 ms 3268 KB Output is correct
11 Correct 10 ms 3264 KB Output is correct
12 Correct 9 ms 3128 KB Output is correct
13 Correct 9 ms 3132 KB Output is correct
14 Correct 9 ms 3132 KB Output is correct
15 Correct 10 ms 3344 KB Output is correct
16 Correct 9 ms 3404 KB Output is correct
17 Correct 10 ms 3400 KB Output is correct
18 Correct 10 ms 3276 KB Output is correct
19 Correct 9 ms 3392 KB Output is correct
20 Correct 9 ms 4036 KB Output is correct
21 Correct 9 ms 4260 KB Output is correct
22 Correct 11 ms 3880 KB Output is correct
23 Correct 11 ms 4072 KB Output is correct
24 Correct 10 ms 3952 KB Output is correct
25 Correct 11 ms 4044 KB Output is correct
26 Correct 11 ms 4136 KB Output is correct
27 Correct 11 ms 4140 KB Output is correct
28 Correct 11 ms 4100 KB Output is correct
29 Correct 9 ms 3856 KB Output is correct
30 Correct 10 ms 3860 KB Output is correct
31 Correct 2 ms 1284 KB Output is correct
32 Correct 2 ms 1288 KB Output is correct
33 Correct 3 ms 1288 KB Output is correct
34 Correct 2 ms 1360 KB Output is correct
35 Correct 2 ms 1360 KB Output is correct
36 Correct 2 ms 1284 KB Output is correct
37 Correct 1 ms 1284 KB Output is correct
38 Correct 2 ms 1356 KB Output is correct
39 Correct 1 ms 1284 KB Output is correct
40 Correct 2 ms 1280 KB Output is correct
41 Correct 2 ms 1296 KB Output is correct
42 Correct 2 ms 1284 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1284 KB Output is correct
2 Correct 2 ms 1292 KB Output is correct
3 Correct 2 ms 1292 KB Output is correct
4 Correct 4 ms 1920 KB Output is correct
5 Correct 3 ms 1928 KB Output is correct
6 Correct 3 ms 1968 KB Output is correct
7 Correct 3 ms 1964 KB Output is correct
8 Correct 3 ms 1968 KB Output is correct
9 Correct 9 ms 5160 KB Output is correct
10 Correct 9 ms 5164 KB Output is correct
11 Correct 10 ms 5160 KB Output is correct
12 Correct 1 ms 1360 KB Output is correct
13 Correct 2 ms 1412 KB Output is correct
14 Correct 1 ms 1284 KB Output is correct
15 Correct 2 ms 1292 KB Output is correct

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5488 KB Output is correct
2 Partially correct 18 ms 5336 KB Partially correct
3 Partially correct 18 ms 5444 KB Partially correct
4 Correct 11 ms 3588 KB Output is correct
5 Correct 12 ms 4724 KB Output is correct
6 Correct 11 ms 4144 KB Output is correct
7 Correct 11 ms 4132 KB Output is correct
8 Correct 11 ms 3768 KB Output is correct
9 Correct 11 ms 3876 KB Output is correct
10 Correct 9 ms 3496 KB Output is correct
11 Correct 9 ms 3496 KB Output is correct
12 Correct 10 ms 3340 KB Output is correct
13 Correct 9 ms 3336 KB Output is correct
14 Correct 11 ms 3360 KB Output is correct
15 Correct 11 ms 3604 KB Output is correct
16 Correct 10 ms 3584 KB Output is correct
17 Correct 10 ms 3492 KB Output is correct
18 Correct 10 ms 3500 KB Output is correct
19 Correct 11 ms 3500 KB Output is correct
20 Incorrect 9 ms 4260 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5392 KB Output is correct
2 Correct 19 ms 5460 KB Output is correct
3 Incorrect 18 ms 5436 KB Output isn't correct
4 Halted 0 ms 0 KB -