oj.uz

답안 #1003650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003650 2024-06-20T14:39:30 Z AdamGS Amusement Park (JOI17_amusement_park) C++17
10 / 100
 15 ms 4668 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()
namespace {
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]) {
    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;
}

Compilation message

Ioi.cpp:14:22: warning: '{anonymous}::jaki' defined but not used [-Wunused-variable]
   14 | ll F[LIM], odl[LIM], jaki[LIM], pre[LIM], oc[LIM], n, X, akt, wierz, licz;
      |                      ^~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2320 KB Wrong Answer [8]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 3932 KB Output is correct
2 Correct 15 ms 4340 KB Output is correct
3 Correct 15 ms 4364 KB Output is correct
4 Incorrect 10 ms 4408 KB Wrong Answer [8]
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1308 KB Output is correct
2 Correct 0 ms 1312 KB Output is correct
3 Correct 0 ms 1312 KB Output is correct
4 Correct 2 ms 1864 KB Output is correct
5 Correct 2 ms 1864 KB Output is correct
6 Correct 1 ms 1856 KB Output is correct
7 Correct 1 ms 1852 KB Output is correct
8 Correct 2 ms 1864 KB Output is correct
9 Correct 8 ms 4668 KB Output is correct
10 Correct 8 ms 4664 KB Output is correct
11 Correct 7 ms 4664 KB Output is correct
12 Correct 0 ms 1300 KB Output is correct
13 Correct 1 ms 1380 KB Output is correct
14 Correct 0 ms 1312 KB Output is correct
15 Correct 0 ms 1312 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 3944 KB Output is correct
2 Correct 15 ms 4424 KB Output is correct
3 Correct 13 ms 4392 KB Output is correct
4 Incorrect 10 ms 4412 KB Wrong Answer [8]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3940 KB Output is correct
2 Correct 14 ms 4384 KB Output is correct
3 Correct 14 ms 4332 KB Output is correct
4 Incorrect 9 ms 4408 KB Wrong Answer [8]
5 Halted 0 ms 0 KB -