| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1174191 | nhphuc | Amusement Park (JOI17_amusement_park) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
namespace {
const int N = 10007;
int par[N], mess[N], leaf;
bool ing[N];
vector<int> g[N], adj[N], group[N];
void bfs (int n, int src){
fill(par, par + n, -1);
queue<int> q;
vector<int> d(n, -1);
d[src] = 0;
q.push(src);
while (q.size()){
int u = q.front(); q.pop();
for (int v : g[u]){
if (d[v] == -1){
par[v] = u;
d[v] = d[u] + 1;
q.push(v);
}
}
}
return;
}
void init (int n){
fill(mess, mess + n, -1);
for (int i = 0; i < n; ++i){
g[i].clear();
adj[i].clear();
}
}
void dfs (int u, int p = -1){
int child = 0;
for (int v : adj[u]){
if (v != p && ing[v]){
++child;
dfs(v, u);
}
}
if (child == 0){
leaf = u;
}
return;
}
void Joi (int n, int m, int a[], int b[], long long x, int subtask){
init(n);
for (int i = 0; i < m; ++i){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
bfs(n, 0);
for (int i = 0; i < n; ++i){
if (par[i] != -1){
adj[i].push_back(par[i]);
adj[par[i]].push_back(i);
}
}
vector<int> st;
{
queue<int> q;
q.push(0);
while (st.size() < 60 && q.size()){
int u = q.front(); q.pop();
mess[u] = st.size();
st.push_back(u);
for (int v : adj[u]){
if (mess[v] == -1){
q.push(v);
}
}
}
}
queue<int> q;
for (int u : st){
group[u] = st;
q.push(u);
}
while (q.size()){
int u = q.front(); q.pop();
for (int v : adj[u]){
if (mess[v] == -1){
for (int uu : group[u]){
ing[uu] = true;
}
dfs(u);
group[v] = group[u];
for (int i = 0; i < group[v].size(); ++i){
if (group[v][i] == leaf){
group[v][i] = v;
}
}
mess[v] = leaf;
for (int uu : group[u]){
ing[uu] = false;
}
}
}
}
for (int i = 0; i < n; ++i){
MessageBoard(i, (x >> mess[i] & 1));
}
return;
}
}
#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
namespace {
const int N = 10007;
int par[N], mess[N], leaf;
bool ing[N];
vector<int> g[N], adj[N], group[N];
void bfs (int n, int src){
fill(par, par + n, -1);
queue<int> q;
vector<int> d(n, -1);
d[src] = 0;
q.push(src);
while (q.size()){
int u = q.front(); q.pop();
for (int v : g[u]){
if (d[v] == -1){
par[v] = u;
d[v] = d[u] + 1;
q.push(v);
}
}
}
return;
}
void init (int n){
fill(mess, mess + n, -1);
for (int i = 0; i < n; ++i){
g[i].clear();
adj[i].clear();
}
}
void dfs (int u, int p = -1){
int child = 0;
for (int v : adj[u]){
if (v != p && ing[v]){
++child;
dfs(v, u);
}
}
if (child == 0){
leaf = u;
}
return;
}
void dfs2 (int u, long long &answer, int p = -1){
for (int v : adj[u]){
if (ing[v] && v != p){
answer += (1ll << mess[v]) * Move(v);
dfs2(v, answer, u);
}
}
if (p != -1){
int f = Move(p);
}
return;
}
long long Ioi (int n, int m, int a[], int b[], int p, int v, int subtask){
init(n);
for (int i = 0; i < m; ++i){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
bfs(n, 0);
for (int i = 0; i < n; ++i){
if (par[i] != -1){
adj[i].push_back(par[i]);
adj[par[i]].push_back(i);
}
}
vector<int> st;
{
queue<int> q;
q.push(0);
while (st.size() < 60 && q.size()){
int u = q.front(); q.pop();
mess[u] = st.size();
st.push_back(u);
for (int v : adj[u]){
if (mess[v] == -1){
q.push(v);
}
}
}
}
queue<int> q;
for (int u : st){
group[u] = st;
q.push(u);
}
while (q.size()){
int u = q.front(); q.pop();
for (int v : adj[u]){
if (mess[v] == -1){
for (int uu : group[u]){
ing[uu] = true;
}
dfs(u);
group[v] = group[u];
for (int i = 0; i < group[v].size(); ++i){
if (group[v][i] == leaf){
group[v][i] = v;
}
}
mess[v] = leaf;
for (int uu : group[u]){
ing[uu] = false;
}
}
}
}
long long answer = (1ll << mess[p]) * v;
for (int uu : group[p]){
ing[uu] = true;
}
dfs2(p, answer);
return answer;
}
}