제출 #929369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
929369		huutuan	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	20 ms	5744 KiB

Joi

#include "Joi.h"

#include<bits/stdc++.h>
using namespace std;

namespace joi{
   #define int long long
   const int N=1e4+10, M=2e4+10;
   int n;
   int m;
   vector<int> g[N];
   pair<int, int> edge[M];
   int dep[N], par[N];
   void dfs_dep(int u){
      for (int v:g[u]) if (dep[v]==-1){
         dep[v]=dep[u]+1;
         par[v]=u;
         dfs_dep(v);
      }
   }
   int vis[N];
   vector<int> chosen;
   vector<int> diameter;
   void dfs_choose(int u){
      if ((int)chosen.size()==60) return;
      for (int v:g[u]) if (!vis[v]){
         if ((int)chosen.size()==60) return;
         vis[v]=1;
         chosen.push_back(v);
         dfs_choose(v);
      }
   }
   int ans[N];
   void solve(int x){
      memset(dep, -1, sizeof dep);
      dep[0]=0; par[0]=-1; dfs_dep(0);
      int u=max_element(dep, dep+n)-dep;
      memset(dep, -1, sizeof dep);
      dep[u]=0; par[u]=-1; dfs_dep(u);
      int max_dep=*max_element(dep, dep+n);
      if (max_dep>=60){
         for (int i=0; i<n; ++i) MessageBoard(i, x>>(dep[i]%60)&1);
      }else{
         int v=max_element(dep, dep+n)-dep;
         while (v!=u) chosen.push_back(v), v=par[v];
         chosen.push_back(u);
         reverse(chosen.begin(), chosen.end());
         diameter=chosen;
         for (int i:diameter) vis[i]=1;
         for (int i:diameter) dfs_choose(i);
         for (int i=0; i<60; ++i) ans[chosen[i]]=x>>i&1;
         for (int i=0; i<n; ++i) MessageBoard(i, ans[i]);
      }
   }
   #undef int
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
   joi::n=N;
   joi::m=M;
   for (int i=0; i<M; ++i){
      joi::g[A[i]].push_back(B[i]);
      joi::g[B[i]].push_back(A[i]);
   }
   joi::solve(X);
}

Ioi

#include "Ioi.h"

#include<bits/stdc++.h>
using namespace std;

namespace ioi{
   #define int long long
   const int N=1e4+10, M=2e4+10;
   int n;
   int m;
   vector<int> g[N];
   pair<int, int> edge[M];
   int dep[N], par[N];
   void dfs_dep(int u){
      for (int v:g[u]) if (dep[v]==-1){
         dep[v]=dep[u]+1;
         par[v]=u;
         dfs_dep(v);
      }
   }
   int vis[N];
   vector<int> chosen;
   vector<int> diameter;
   vector<int> gg[N];
   void dfs_choose(int u){
      if ((int)chosen.size()==60) return;
      for (int v:g[u]) if (!vis[v]){
         if ((int)chosen.size()==60) return;
         vis[v]=1;
         gg[u].push_back(v);
         chosen.push_back(v);
         dfs_choose(v);
      }
   }
   int ans[N];
   void dfs(int u){
      if (find(diameter.begin(), diameter.end(), u)==diameter.end()){
         for (int v:gg[u]){
            if (find(chosen.begin(), chosen.end(), v)==chosen.end()) continue;
            if (find(diameter.begin(), diameter.end(), v)==diameter.end()){
               ans[v]=Move(v);
               dfs(v);
               Move(u);
            }
         }
         return;
      }
      for (int v:gg[u]) if (v!=gg[u][0]){
         if (find(chosen.begin(), chosen.end(), v)==chosen.end()) continue;
         if (find(diameter.begin(), diameter.end(), v)==diameter.end()){
            ans[v]=Move(v);
            dfs(v);
            Move(u);
         }
      }
      if (gg[u].size()){
         int v=gg[u][0];
         ans[v]=Move(v);
         return dfs(v);
      }
   }
   int solve(int x, int y){
      ans[x]=y;
      memset(dep, -1, sizeof dep);
      dep[0]=0; par[0]=-1; dfs_dep(0);
      int u=max_element(dep, dep+n)-dep;
      memset(dep, -1, sizeof dep);
      dep[u]=0; par[u]=-1; dfs_dep(u);
      int max_dep=*max_element(dep, dep+n);
      if (max_dep>=60){
         if (dep[x]>=59){
            vector<int> path;
            path.push_back(x);
            while ((int)path.size()!=60){
               x=par[x];
               ans[x]=Move(x);
               path.push_back(x);
            }
            int res=0;
            for (int i:path) res|=ans[i]<<(dep[i]%60);
            return res;
         }
         while (x!=u) x=par[x], ans[x]=Move(x);
         int v=max_element(dep, dep+n)-dep;
         vector<int> path;
         while (v!=u) path.push_back(v), v=par[v];
         path.push_back(u);
         reverse(path.begin(), path.end());
         path.resize(60);
         for (int i=1; i<60; ++i) ans[path[i]]=Move(path[i]);
         int res=0;
         for (int i:path) res|=ans[i]<<(dep[i]%60);
         return res;
      }else{
         int v=max_element(dep, dep+n)-dep;
         while (v!=u) chosen.push_back(v), v=par[v];
         chosen.push_back(u);
         reverse(chosen.begin(), chosen.end());
         diameter=chosen;
         for (int i:diameter) vis[i]=1;
         for (int i=0; i<(int)diameter.size()-1; ++i) gg[diameter[i]].push_back(diameter[i+1]);
         for (int i:diameter) dfs_choose(i);
         while (x!=u) x=par[x], ans[x]=Move(x);
         dfs(x);
         int res=0;
         for (int i=0; i<60; ++i) res|=ans[chosen[i]]<<i;
         return res;
      }
      return -1;
   }
   #undef int
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
   ioi::n=N;
   ioi::m=M;
   for (int i=0; i<M; ++i){
      ioi::g[A[i]].push_back(B[i]);
      ioi::g[B[i]].push_back(A[i]);
   }
   return ioi::solve(P, V);
}

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