oj.uz

Submission #1003654

# Submission time Handle Problem Language Result Execution time Memory
1003654 2024-06-20T14:41:32 Z AdamGS Amusement Park (JOI17_amusement_park) C++17
79 / 100
 16 ms 4428 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e4+7;
vector<int>V[LIM];
ll F[LIM], odl[LIM], jaki[LIM], pre[LIM], n, X, akt;
int fnd(int x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
bool uni(int a, int b) {
  if(fnd(a)==fnd(b)) return false;
  F[fnd(b)]=fnd(a);
  return true;
}
void DFS(int x, int o) {
  pre[x]=akt++;
  for(auto i : V[x]) if(i!=o) {
    odl[i]=odl[x]+1;
    DFS(i, x);
  }
}
void Joi(int _n, int _m, int _A[], int _B[], ll _X, int _T) {
  n=_n; X=_X;
  rep(i, n) F[i]=i;
  rep(i, _m) if(uni(_A[i], _B[i])) {
    V[_A[i]].pb(_B[i]);
    V[_B[i]].pb(_A[i]);
  }
  DFS(0, 0);
  bool gleb=false;
  rep(i, n) if(odl[i]>=59) gleb=true;
  if(gleb) {
    rep(i, n) if(X&(1ll<<(ll)(odl[i]%60))) jaki[i]=1;
  } else {
    rep(i, n) if(X&(1ll<<(ll)(pre[i]%60))) jaki[i]=1;
  }
  rep(i, n) MessageBoard(i, jaki[i]);
}

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e4+7;
vector<int>V[LIM];
bool kon=false;
ll F[LIM], odl[LIM], jaki[LIM], pre[LIM], oc[LIM], n, X, akt, wierz, licz;
int fnd(int x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
bool uni(int a, int b) {
  if(fnd(a)==fnd(b)) return false;
  F[fnd(b)]=fnd(a);
  return true;
}
void DFS(int x, int o) {
  pre[x]=akt++;
  for(auto i : V[x]) if(i!=o) {
    odl[i]=odl[x]+1;
    oc[i]=x;
    DFS(i, x);
  }
}
void DFS2(int x, int o) {
  if(licz) X|=1ll<<(ll)(pre[x]%60);
  if(pre[x]==59) kon=true;
  for(auto i : V[x]) if(i!=o) {
    licz=Move(i);
    wierz=i;
    DFS2(i, x);
    if(kon) return;
    licz=Move(x);
    wierz=x;
  }
}
ll Ioi(int _n, int _m, int _A[], int _B[], int _P, int _V, int _T) {
  n=_n; wierz=_P; licz=_V;
  rep(i, n) F[i]=i;
  rep(i, _m) if(uni(_A[i], _B[i])) {
    V[_A[i]].pb(_B[i]);
    V[_B[i]].pb(_A[i]);
  }
  DFS(0, 0);
  if(odl[wierz]>=59) {
    if(licz) X|=1ll<<(ll)(odl[wierz]%60);
    rep(i, 59) {
      licz=Move(oc[wierz]);
      wierz=oc[wierz];
      if(licz) X|=1ll<<(ll)(odl[wierz]%60);
    }
    return X;
  }
  while(wierz) {
    licz=Move(oc[wierz]);
    wierz=oc[wierz];
  }
  rep(i, n) if(odl[i]==59) {
    vector<ll>A;
    int x=i;
    while(x) {
      A.pb(x);
      x=oc[x];
    }
    reverse(all(A));
    if(licz) X|=1ll<<(ll)(odl[wierz]%60);
    for(auto j : A) {
      licz=Move(j);
      wierz=j;
      if(licz) X|=1ll<<(ll)(odl[wierz]%60);
    }
    return X;
  }
  DFS2(0, 0);
  return X;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1560 KB Output is correct
2 Correct 0 ms 1296 KB Output is correct
3 Correct 0 ms 1308 KB Output is correct
4 Correct 0 ms 1312 KB Output is correct
5 Correct 0 ms 1312 KB Output is correct
6 Correct 1 ms 1300 KB Output is correct
7 Correct 0 ms 1308 KB Output is correct
8 Correct 0 ms 1316 KB Output is correct
9 Correct 0 ms 1308 KB Output is correct
10 Correct 1 ms 1312 KB Output is correct
11 Correct 2 ms 1376 KB Output is correct
12 Correct 0 ms 1300 KB Output is correct
13 Correct 1 ms 1308 KB Output is correct
14 Correct 1 ms 1316 KB Output is correct
15 Correct 2 ms 1320 KB Output is correct
16 Correct 1 ms 1316 KB Output is correct
17 Correct 1 ms 1316 KB Output is correct
18 Correct 1 ms 1316 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3760 KB Output is correct
2 Correct 16 ms 3944 KB Output is correct
3 Correct 14 ms 3944 KB Output is correct
4 Correct 9 ms 3296 KB Output is correct
5 Correct 9 ms 3900 KB Output is correct
6 Correct 9 ms 3896 KB Output is correct
7 Correct 9 ms 3900 KB Output is correct
8 Correct 9 ms 3904 KB Output is correct
9 Correct 11 ms 3888 KB Output is correct
10 Correct 7 ms 3412 KB Output is correct
11 Correct 7 ms 3396 KB Output is correct
12 Correct 8 ms 3320 KB Output is correct
13 Correct 7 ms 3368 KB Output is correct
14 Correct 7 ms 3372 KB Output is correct
15 Correct 9 ms 3380 KB Output is correct
16 Correct 8 ms 3384 KB Output is correct
17 Correct 11 ms 3384 KB Output is correct
18 Correct 9 ms 3384 KB Output is correct
19 Correct 9 ms 3380 KB Output is correct
20 Correct 7 ms 3892 KB Output is correct
21 Correct 7 ms 4120 KB Output is correct
22 Correct 12 ms 3904 KB Output is correct
23 Correct 10 ms 3908 KB Output is correct
24 Correct 11 ms 4228 KB Output is correct
25 Correct 9 ms 3896 KB Output is correct
26 Correct 9 ms 3896 KB Output is correct
27 Correct 9 ms 3904 KB Output is correct
28 Correct 9 ms 3884 KB Output is correct
29 Correct 7 ms 3872 KB Output is correct
30 Correct 11 ms 3880 KB Output is correct
31 Correct 1 ms 1296 KB Output is correct
32 Correct 0 ms 1300 KB Output is correct
33 Correct 0 ms 1316 KB Output is correct
34 Correct 0 ms 1300 KB Output is correct
35 Correct 1 ms 1300 KB Output is correct
36 Correct 0 ms 1312 KB Output is correct
37 Correct 1 ms 1312 KB Output is correct
38 Correct 1 ms 1380 KB Output is correct
39 Correct 0 ms 1300 KB Output is correct
40 Correct 0 ms 1312 KB Output is correct
41 Correct 0 ms 1312 KB Output is correct
42 Correct 0 ms 1308 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1308 KB Output is correct
2 Correct 1 ms 1304 KB Output is correct
3 Correct 0 ms 1308 KB Output is correct
4 Correct 3 ms 1844 KB Output is correct
5 Correct 2 ms 1836 KB Output is correct
6 Correct 2 ms 1724 KB Output is correct
7 Correct 2 ms 1852 KB Output is correct
8 Correct 1 ms 1840 KB Output is correct
9 Correct 5 ms 4312 KB Output is correct
10 Correct 7 ms 4324 KB Output is correct
11 Correct 5 ms 4428 KB Output is correct
12 Correct 0 ms 1304 KB Output is correct
13 Correct 0 ms 1308 KB Output is correct
14 Correct 0 ms 1296 KB Output is correct
15 Correct 1 ms 1304 KB Output is correct

Subtask #4
51.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3936 KB Output is correct
2 Correct 12 ms 3936 KB Output is correct
3 Correct 12 ms 3936 KB Output is correct
4 Correct 8 ms 3296 KB Output is correct
5 Correct 8 ms 4408 KB Output is correct
6 Correct 8 ms 3916 KB Output is correct
7 Correct 10 ms 3896 KB Output is correct
8 Correct 9 ms 3904 KB Output is correct
9 Correct 9 ms 4156 KB Output is correct
10 Correct 7 ms 3484 KB Output is correct
11 Correct 8 ms 3480 KB Output is correct
12 Correct 9 ms 3368 KB Output is correct
13 Partially correct 8 ms 3256 KB Partially correct
14 Partially correct 8 ms 3376 KB Partially correct
15 Correct 9 ms 3392 KB Output is correct
16 Correct 9 ms 3380 KB Output is correct
17 Correct 7 ms 3380 KB Output is correct
18 Partially correct 9 ms 3500 KB Partially correct
19 Partially correct 9 ms 3384 KB Partially correct
20 Correct 6 ms 3904 KB Output is correct
21 Correct 6 ms 3904 KB Output is correct
22 Correct 9 ms 3904 KB Output is correct
23 Correct 9 ms 3852 KB Output is correct
24 Correct 9 ms 3904 KB Output is correct
25 Correct 8 ms 3896 KB Output is correct
26 Correct 9 ms 3900 KB Output is correct
27 Correct 7 ms 3904 KB Output is correct
28 Correct 7 ms 3900 KB Output is correct
29 Correct 7 ms 3836 KB Output is correct
30 Correct 7 ms 3888 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3936 KB Output is correct
2 Correct 14 ms 4188 KB Output is correct
3 Correct 15 ms 3940 KB Output is correct
4 Correct 9 ms 3288 KB Output is correct
5 Correct 9 ms 4416 KB Output is correct
6 Correct 9 ms 3888 KB Output is correct
7 Correct 8 ms 3908 KB Output is correct
8 Correct 9 ms 3908 KB Output is correct
9 Correct 9 ms 3900 KB Output is correct
10 Correct 7 ms 3400 KB Output is correct
11 Correct 7 ms 3396 KB Output is correct
12 Correct 7 ms 3368 KB Output is correct
13 Incorrect 7 ms 3368 KB Output isn't correct
14 Halted 0 ms 0 KB -