제출 #1174606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174606		Zero_OP	Amusement Park (JOI17_amusement_park)	C++20	10 / 100	16 ms	2632 KiB

Joi

#include "Joi.h"
#include "bits/stdc++.h"

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back

#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vb = vector<bool>;
using vc = vector<char>;

struct DSU{
      vector<int> lab;
      DSU(int n) : lab(n, -1) {}

      int root(int u){
            return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
      }

      bool join(int u, int v){
            u = root(u);
            v = root(v);
            if(u == v) return false;
            if(lab[u] > lab[v]) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
            return true;
      }
};

const int MAX = 1e4 + 5;

int N, depth[MAX], par[MAX], sub[MAX], c[MAX], mx[MAX], timer_dfs;
vi adj[MAX];

void dfs_len(int u, int p){
      for(auto v : adj[u]) if(v != p){
            depth[v] = depth[u] + 1;
            dfs_len(v, u);
      }
}

void dfs_sz(int u, int p){
      sub[u] = 1;
      for(auto v : adj[u]) if(v != p){
            dfs_sz(v, u);
            sub[u] += sub[v];
      }
}

int find_centroid(int u, int p){
      for(auto v : adj[u]) if(v != p && sub[v] * 2 > N){
            return find_centroid(v, u);
      }
      return u;
}

tuple<int, int, int> find_diameter(){
      depth[0] = 0;
      dfs_len(0, -1);
      int L1 = max_element(depth, depth + N) - depth;

      depth[L1] = 0;
      dfs_len(L1, -1);
      int L2 = max_element(depth, depth + N) - depth;

      return mt(L1, L2, depth[L2]);
}

void dfs_root(int u, ll X){
      c[u] = (depth[u] % 60);
      mx[u] = depth[u];
      for(auto v : adj[u]){
            adj[v].erase(find(all(adj[v]), u));
            depth[v] = depth[u] + 1;
            par[v] = u;
            dfs_root(v, X);
            maximize(mx[u], mx[v]);
      }
}

void dfs_root2(int u){
      mx[u] = depth[u];
      for(auto v : adj[u]){
            adj[v].erase(find(all(adj[v]), u));
            depth[v] = depth[u] + 1;
            par[v] = u;
            dfs_root2(v);
            maximize(mx[u], mx[v]);
      }
}

void dfs_mark(int u, ll X){
      if(timer_dfs == 60) return;
      c[u] = (X >> (timer_dfs++) & 1);
      for(auto v : adj[u]){
            dfs_mark(v, X);
      }
}

void add(int u, int pre, int& need, vi& vis){
      if(!need) return;
      vis.pb(u);
      --need;
//      cout << "ss : " << u << '\n';
      for(auto v : adj[u]){
            add(v, u, need, vis);
      }
      vis.pb(pre);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
      DSU dsu(N);
      ::N = N;
      FOR(i, 0, M){
            if(dsu.join(A[i], B[i])){
                  adj[A[i]].pb(B[i]);
                  adj[B[i]].pb(A[i]);
            }
      }

      int L1, L2, dist;
      tie(L1, L2, dist) = find_diameter();

      FOR(i, 0, N) c[i] = -1;

      if(dist >= 59){
            //root tree at L1
            depth[L1] = 0;
            dfs_root(L1, X);
      } else{
            dfs_sz(0, -1);
            int centroid = find_centroid(0, -1);

            depth[centroid] = 0;
            dfs_root2(centroid);


//            cout << dbg(centroid) << "JOI\n";
            FOR(i, 0, N) sort(all(adj[i]), [&](int a, int b){ return mx[a] > mx[b]; });

            int low = -1;
//            FOR(i, 0, N) cout << depth[i] << " \n"[i == N-1];
            FOR(i, 0, N) if(low == -1 || depth[low] < depth[i]) low = i;
//            cout << dbg(low) << '\n';
            vb one_time_called(N, false);

            vector<vi> visits;

            int u = low;
            while(u != centroid){
                  one_time_called[u] = true;
                  visits.pb({u});
                  u = par[u];
            }
            one_time_called[centroid] = true;
            visits.pb({centroid});

            reverse(all(visits));
            int need = 60 - sz(visits);
            FOR(i, 0, sz(visits)){
                  int r = visits[i][0];
                  for(auto child : adj[r]){
                        if(!one_time_called[child]){
                              add(child, r, need, visits[i]);
                        }
                  }
            }

//            cout << '\n';
//
//            cout << "tour JOI : ";

            FOR(i, 0, sz(visits)){
                  for(auto j : visits[i]){
                        if(c[j] == -1) {
                              c[j] = timer_dfs++;
//                              cout << j << ' ';
                        }
                  }
            }

//            cout << '\n';
      }

      FOR(i, 0, N){
            MessageBoard(i, (c[i] == -1 ? 0 : (X >> c[i] & 1)));
      }
}

Ioi

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

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back

#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vb = vector<bool>;
using vc = vector<char>;

struct DSU{
      vector<int> lab;
      DSU(int n) : lab(n, -1) {}

      int root(int u){
            return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
      }

      bool join(int u, int v){
            u = root(u);
            v = root(v);
            if(u == v) return false;
            if(lab[u] > lab[v]) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
            return true;
      }
};

const int MAX = 1e4 + 5;

int _N, _depth[MAX], _par[MAX], _sub[MAX], _c[MAX], _mx[MAX], _timer_dfs;
vi _adj[MAX], _adj_general[MAX];

void _dfs_len(int u, int p){
      for(auto v : _adj[u]) if(v != p){
            _depth[v] = _depth[u] + 1;
            _dfs_len(v, u);
      }
}

void _dfs_sz(int u, int p){
      _sub[u] = 1;
      for(auto v : _adj[u]) if(v != p){
            _dfs_sz(v, u);
            _sub[u] += _sub[v];
      }
}

int _find_centroid(int u, int p){
      for(auto v : _adj[u]) if(v != p && _sub[v] * 2 > _N){
            return _find_centroid(v, u);
      }
      return u;
}

tuple<int, int, int> _find_diameter(){
      _depth[0] = 0;
      _dfs_len(0, -1);
      int L1 = max_element(_depth, _depth + _N) - _depth;

      _depth[L1] = 0;
      _dfs_len(L1, -1);
      int L2 = max_element(_depth, _depth + _N) - _depth;

      return mt(L1, L2, _depth[L2]);
}

void _dfs_root(int u){
      _c[u] = (_depth[u] % 60);
      _mx[u] = _depth[u];
      for(auto v : _adj[u]){
            _adj[v].erase(find(all(_adj[v]), u));
            _depth[v] = _depth[u] + 1;
            _par[v] = u;
            _dfs_root(v);
            maximize(_mx[u], _mx[v]);
      }
}

int MoveTo(int S, int SV, int T){
      //return TV

      if(S == T) return SV;

      queue<int> q;
      vi pre(_N, -1), d(_N, -1);

      q.push(S);
      d[S] = 0;

      while(!q.empty()){
            int u = q.front(); q.pop();
            for(auto v : _adj_general[u]){
                  if(d[v] == -1){
                        d[v] = d[u] + 1;
                        pre[v] = u;
                        q.push(v);
                  }
            }
      }

      stack<int> st;
      int u = T;
      while(T != S){
            assert(T != -1);
            st.push(T);
            T = pre[T];
      }

      int val = SV;
      while(!st.empty()){
            u = st.top(); st.pop();
            val = Move(u);
      }
      return val;
}

void _add(int u, int pre, int& need, vi& vis){
      if(!need) return;
      vis.pb(u);
      --need;
//      cout << "insert in : " << u << '\n';
      for(auto v : _adj[u]){
            _add(v, u, need, vis);
      }
//      cout << "insert out : " << pre << '\n';
      vis.pb(pre);
}

long long Ioi(int _N, int M, int A[], int B[], int P, int V, int T) {
      DSU dsu(_N);
      ::_N = _N;
      FOR(i, 0, M){
            if(dsu.join(A[i], B[i])){
                  _adj[A[i]].pb(B[i]);
                  _adj[B[i]].pb(A[i]);
            }

            _adj_general[A[i]].pb(B[i]);
            _adj_general[B[i]].pb(A[i]);
      }

      int L1, L2, dist;
      tie(L1, L2, dist) = _find_diameter();

      FOR(i, 0, _N) _c[i] = -1;

      ll X = 0;
      if(dist >= 59){
            //root tree at L1
            _depth[L1] = 0;
            _dfs_root(L1);
            FOR(i, 0, _N) sort(all(_adj[i]), [&](int a, int b){ return _mx[a] > _mx[b]; });

            if(_depth[P] >= 59){
                  X |= (1LL << (_c[P])) * V;
                  FOR(i, 0, 59){
                        P = _par[P];
                        V = Move(P);
                        X |= (1LL << (_c[P])) * V;
                  }
            } else{
                  while(P != L1){
                        P = _par[P];
                        V = Move(P);
                  }

                  X |= (1LL << (_c[P])) * V;
                  FOR(i, 0, 59){
                        int nxt = -1;
                        for(auto u : _adj[P]){
                              if(_mx[u] >= 59){
                                    nxt = u;
                                    break;
                              }
                        }

                        assert(nxt != -1);
                        P = nxt;
                        V = Move(P);
                        X |= (1LL << (_c[P])) * V;
                  }
            }
      } else{
            _dfs_sz(0, -1);
            int centroid = _find_centroid(0, -1);

//            cout << "before : " << X << '\n';
//            cout << dbg(centroid) << "IOI\n";
            _depth[centroid] = 0;
            _dfs_root(centroid);
            FOR(i, 0, _N) sort(all(_adj[i]), [&](int a, int b){ return _mx[a] > _mx[b]; });

            V = MoveTo(P, V, centroid);

            int low = -1;
//            FOR(i, 0, _N) cout << _depth[i] << " \n"[i == _N-1];
            FOR(i, 0, _N) if(low == -1 || _depth[low] < _depth[i]) low = i;
//            cout << dbg(low) << '\n';
            vb one_time_called(_N, false);

            vector<vi> visits;

            int u = low;
            while(u != centroid){
                  one_time_called[u] = true;
                  visits.pb({u});
                  u = _par[u];
            }

            one_time_called[centroid] = true;
            visits.pb({centroid});

            reverse(all(visits));
            int need = 60 - sz(visits);
//            cout << need << '\n';
            FOR(i, 0, sz(visits)){
                  int r = visits[i][0];
                  for(auto child : _adj[r]){
                        if(!one_time_called[child]){
                              _add(child, r, need, visits[i]);
                        }
                  }
            }

//            cout << '\n';
//            cout << "tour IOI : ";

            vi tour;
            FOR(i, 0, sz(visits)){
                  for(auto j : visits[i]){
//                        cout << j << ' ';
                        if(_c[j] == -1) {
                              _c[j] = _timer_dfs++;
//                              cout << j << ' ';
                        }
                        tour.pb(j);
                  }
            }

//            cout << '\n';
//            cout << X << '\n';

            X |= (1LL << (_c[centroid])) * V;
//            cout << X << '\n';
            FOR(i, 1, sz(tour)){
                  V = Move(tour[i]);
                  X |= (1LL << (_c[tour[i]])) * V;
//                  cout << "bum : " << X << '\n';
            }
      }
      return X;
}

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