| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 553962 | nafis_shifat | Amusement Park (JOI17_amusement_park) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "Joi.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
vector<int> g[mxn];
vector<int> adj[mxn];
int n;
int vis[mxn] = {};
const int SZ = 60;
void dfs0(int u) {
vis[u] = 1;
for(int v : g[u]) {
if(vis[v]) continue;
adj[u].push_back(v);
adj[v].push_back(u);
dfs0(v);
}
}
int bit[mxn] = {};
int group[mxn] = {};
vector<int> con[mxn];
int id = 0;
int done[mxn] = {};
vector<int> dfs(int u, int prev) {
vector<int> cur;
cur.push_back(u);
for(int v : adj[u]) {
if(v == prev) continue;
vector<int> x = dfs(v, u);
for(int i : x) cur.push_back(i);
}
if(cur.size() < SZ) return cur;
id++;
for(int i = 0; i < SZ; i++) {
group[cur[i]] = id;
bit[cur[i]] = i;
con[id].push_back(cur[i]);
done[cur[i]] = 1;
}
return {};
}
vector<int> Vis;
void travel(int u, int prev) {
Vis.push_back(u);
done[u] = 1;
for(int v : adj[u]) {
if(v == prev || done[v]) continue;
travel(v, u);
}
}
bool na[mxn] = {};
vector<int> na_con;
void dfs2(int u, int prev) {
na_con.push_back(u);
for(int v : adj[u]) {
if(v == prev || !na[v]) continue;
dfs2(v, u);
}
}
void prc() {
for(int i = 0; i < n; i++) {
if(!done[i]) continue;
for(int j : con[group[i]]) na[j] = 1;
for(int u : adj[i]) {
if(done[u]) continue;
id++;
Vis.clear();
travel(u, -1);
assert(Vis.size() < SZ);
int sz = Vis.size();
int rem = SZ - sz;
na_con.clear();
dfs2(i, -1);
set<int> bt;
for(int j = 0; j < SZ; j++) bt.insert(j);
for(int j = 0; j < rem; j++) {
bt.erase(bit[na_con[j]]);
con[id].push_back(na_con[j]);
}
for(int j = 0; j < sz; j++) {
con[id].push_back(Vis[j]);
bit[Vis[j]] = *bt.begin();
bt.erase(bt.begin());
group[Vis[j]] = id;
done[Vis[j]] = 1;
}
}
for(int j : con[group[i]]) na[j] = 0;
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
n = N;
for(int i = 0; i < M; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs0(0);
dfs(0, -1);
prc();
// for(int i = 1; i <= id; i++) {
// cout<<"GROUP "<<i<<": ";
// for(int j : con[i]) cout<<j<<" ";
// cout<<endl;
// }
for(int i = 0; i < n; i++) {
assert(done[i]);
MessageBoard(i, ((X >> bit[i]) & 1));
}
}