Submission #1003670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003670		AdamGS	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	15 ms	4416 KiB

Joi

#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], czy[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 DFS2(int x, int o, int k) {
  if(x==k) czy[x]=1;
  for(auto i : V[x]) if(i!=o) {
    DFS2(i, x, k);
    if(czy[i]) czy[x]=1;
  }
}
void DFS3(int x, int o) {
  pre[x]=akt++;
  for(auto i : V[x]) if(i!=o && czy[i]) DFS3(i, x);
  for(auto i : V[x]) if(i!=o && !czy[i]) DFS3(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 {
    pair<int,int>ma={-1, -1};
    rep(i, n) ma=max(ma, {odl[i], i});
    DFS2(0, 0, ma.nd);
    akt=0;
    DFS3(0, 0);
    rep(i, n) if(X&(1ll<<(ll)(pre[i]%60))) jaki[i]=1;
  }
  rep(i, n) MessageBoard(i, jaki[i]);
}

Ioi

#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], sciezka;
bool kon=false;
ll F[LIM], odl[LIM], jaki[LIM], pre[LIM], czy[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;
  }
}
void DFS3(int x, int o, int k) {
  if(x==k) czy[x]=1;
  for(auto i : V[x]) if(i!=o) {
    DFS3(i, x, k);
    if(czy[i]) czy[x]=1;
  }
}
void DFS4(int x, int o) {
  pre[x]=akt++;
  for(auto i : V[x]) if(i!=o && czy[i]) {
    bool czy=akt<60;
    DFS4(i, x);
    if(czy) sciezka.pb(i);
  }
  for(auto i : V[x]) if(i!=o && !czy[i]) {
    bool czy=akt<60;
    if(czy) sciezka.pb(x);
    DFS4(i, x);
    if(czy) sciezka.pb(i);
  }
}
}
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;
  }
  pair<int,int>ma={-1, -1};
  rep(i, n) ma=max(ma, {odl[i], i});
  DFS3(0, 0, ma.nd);
  akt=0;
  DFS4(0, 0);
  reverse(all(sciezka));
  if(licz) X|=1ll<<(ll)(pre[wierz]%60);
  for(auto i : sciezka) {
    licz=Move(i);
    wierz=i;
    if(licz) X|=1ll<<(ll)(pre[wierz]%60);
  }
  return X;
}

Compilation message (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17