Submission #1145312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145312		byunjaewoo	Amusement Park (JOI17_amusement_park)	C++20	0 / 100	31 ms	2088 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int N=10010;
int p1, g1[N], num1[N];
bool chk[N], visited[N];
vector<int> adj[N];

void dfs(int curr, int dist, vector<pair<int, int>> &v) {
  v.push_back({curr, dist}), chk[curr]=true;
  for(int next:adj[curr]) if(!chk[next]) dfs(next, dist+1, v);
}

void dfs2(int curr, int dist, vector<pair<int, int>> &v) {
  visited[curr]=true;
  v.push_back({dist, curr});
  for(int next:adj[curr]) if(g1[next]==g1[curr] && !visited[next]) dfs2(next, dist+1, v);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  for(int i=0; i<M; i++) adj[A[i]].push_back(B[i]), adj[B[i]].push_back(A[i]);
  for(int i=0; i<N; i++) if(!chk[i]) {
    vector<pair<int, int>> v;
    dfs(i, 0, v);
    if(v.size()>=60) {
      ++p1;
      for(int j=0; j<60; j++) MessageBoard(v[j].first, (X>>j)&1ll), g1[v[j].first]=p1, num1[v[j].first]=j;
      for(int j=60; j<v.size(); j++) chk[v[j].first]=false;
    }
    else {
      vector<pair<int, int>> v2;
      for(int j:adj[i]) if(g1[j]) {
        fill(visited, visited+N, false);
        dfs2(j, 0, v2); break;
      }
      sort(v2.rbegin(), v2.rend());
      for(auto j:v) MessageBoard(j.first, (X>>num1[v2[j.second].second])&1);
    }
  }
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int N_=10010;
int p, g[N_], num[N_], dist[N_], prv[N_], ans[60];
bool chk1[N_], chk2[N_], visited1[N_];
vector<int> adj1[N_];
queue<int> q;

void dfs1(int curr, int dist, vector<pair<int, int>> &v) {
  v.push_back({curr, dist}), chk1[curr]=true;
  for(int next:adj1[curr]) if(!chk1[next]) dfs1(next, dist+1, v);
}

void bfs(int N, int start) {
  fill(dist, dist+N, N), dist[start]=0, q.push(start);
  while(!q.empty()) {
    int curr=q.front(); q.pop();
    for(int next:adj1[curr]) if(dist[next]>dist[curr]+1) {
      prv[next]=curr, dist[next]=dist[curr]+1, q.push(next);
    }
  }
}

void dfs3(int curr, int dist, vector<pair<int, int>> &v) {
  visited1[curr]=true;
  v.push_back({dist, curr});
  for(int next:adj1[curr]) if(g[next]==g[curr] && !visited1[next]) dfs3(next, dist+1, v);
}

void dfs2(int curr) {
  for(int next:adj1[curr]) if(g[next]==g[curr] && ans[num[next]]<0) {
    ans[num[next]]=Move(next);
    dfs2(next);
    Move(curr);
  }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  for(int i=0; i<M; i++) adj1[A[i]].push_back(B[i]), adj1[B[i]].push_back(A[i]);
  for(int i=0; i<N; i++) if(!chk1[i]) {
    vector<pair<int, int>> v;
    dfs1(i, 0, v);
    if(v.size()>=60) {
      ++p;
      for(int j=0; j<60; j++) num[v[j].first]=j, g[v[j].first]=p;
      for(int j=60; j<v.size(); j++) chk1[v[j].first]=false;
    }
    else {
      vector<pair<int, int>> v2;
      for(int j:adj1[i]) if(g[j]) {
        fill(visited1, visited1+N, false);
        dfs3(j, 0, v2); break;
      }
      sort(v2.rbegin(), v2.rbegin());
      for(auto j:v) num[j.first]=num[v2[j.second].second];
    }
  }
  fill(ans, ans+60, -1);
  if(!g[P]) {
    bfs(N, P);
    int t=-1;
    vector<int> path;
    for(int i=0; i<N; i++) if(num[i]>=0 && (t<0 || dist[i]<dist[t])) t=i;
    while(t!=P) path.push_back(t), t=prv[t];
    reverse(path.begin(), path.end());
    for(int i:path) ans[num[P]]=V, P=i, V=Move(i);
  }
  ans[num[P]]=V;
  dfs2(P);
  ll ret=0;
  for(int i=0; i<60; i++) if(ans[i]) ret+=(1ll<<i);
  return ret;
}

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