| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1145309 | byunjaewoo | Amusement Park (JOI17_amusement_park) | C++20 | 0 ms | 0 KiB |
#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);
}
}
}
#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, 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;
}