| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1370098 | bronze_coder | 저장 (Saveit) (IOI10_saveit) | C++20 | 0 ms | 0 KiB |
#include "encoder.h"
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
vector<int> e;
DSU(int n){
for(int i=0;i<n;i++){
e.push_back(-1);
}
}
int find(int i){
if(e[i]<0){
return i;
}
e[i] = find(e[i]);
return e[i];
}
bool join(int i,int j){
int x = find(i);
int y = find(j);
if(x==y){
return 0;
}
if(e[x]>e[y]){
swap(x,y);
}
e[x] += e[y];
e[y] = x;
return 1;
}
};
void encode(int n,int h,int p,vector<int> a,vector<int> b){
vector<vector<int>> adj(n);
for(int i=0;i<p;i++){
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
vector<pair<int,int>> edges;
DSU dsu(n);
for(int i=0;i<p;i++){
if(dsu.join(a[i],b[i])){
edges.push_back({a[i],b[i]});
}
}
sort(edges.begin(),edges.end());
int cur = 0;
for(int i=0;i<n-1;i++){
while(cur<edges[i].first){
encode_bit(1);
cur++;
}
encode_bit(0);
for(int j=0;j<10;j++){
if(edges[i].second&(1<<j)){
encode_bit(1);
}
else{
encode_bit(0);
}
}
}
int dist[h][n];
for(int i=0;i<h;i++){
for(int j=0;j<n;j++){
dist[i][j] = n;
}
dist[i][i] = 0;
}
for(int i=0;i<h;i++){
vector<int> q = {i};
for(int j=0;j<n;j++){
for(int k:adj[q[j]]){
if(dist[i][k]==n){
dist[i][k] = dist[i][q[j]]+1;
q.push_back(k);
}
}
}
for(int j=0;j<n;j++){
cout << "DIST " << i << " " << j << " " << dist[i][j] << endl;
}
}
vector<int> q = {0};
vector<vector<int>> adj1(n);
for(int i=0;i<n-1;i++){
adj1[edges[i].first].push_back(edges[i].second);
adj1[edges[i].second].push_back(edges[i].first);
}
vector<int> parent(n,-1);
for(int i=0;i<n;i++){
for(int j:adj1[q[i]]){
if(j!=parent[i]){
parent[j] = i;
q.push_back(j);
}
}
}
for(int i=0;i<h;i++){
for(int j=0;j<10;j++){
if(dist[i][0]&(1<<j)){
encode_bit(1);
}
else{
encode_bit(0);
}
}
vector<int> ternary;
for(int j=1;j<n;j++){
int x = dist[i][q[j]]-dist[i][parent[q[j]]];
ternary.push_back(x+1);
}
while(ternary.size()%5!=0){
ternary.push_back(0);
}
for(int j=0;j<ternary.size();j+=5){
int x = 81*ternary[j]+27*ternary[j+1]+9*ternary[j+2]+3*ternary[j+3]+ternary[j+4];
for(int k=0;k<8;k++){
if(x&(1<<k)){
encode_bit(1);
}
else{
encode_bit(0);
}
}
}
}
}#include "decoder.h"
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
void decode(int n,int h){
vector<pair<int,int>> edges;
int cur = 0;
while(edges.size()<n-1){
if(decode_bit()){
cur++;
}
else{
int x = 0;
for(int i=0;i<10;i++){
if(decode_bit()){
x += 1<<i;
}
}
edges.push_back({cur,x});
}
}
vector<int> q = {0};
vector<vector<int>> adj1(n);
for(int i=0;i<n-1;i++){
adj1[edges[i].first].push_back(edges[i].second);
adj1[edges[i].second].push_back(edges[i].first);
}
vector<int> parent(n,-1);
for(int i=0;i<n;i++){
for(int j:adj1[q[i]]){
if(j!=parent[i]){
parent[j] = i;
q.push_back(j);
}
}
}
for(int i=0;i<h;i++){
vector<int> dist(n,0);
for(int j=0;j<10;j++){
if(decode_bit()){
dist[0] += 1<<j;
}
}
vector<int> ternary;
while(ternary.size()<n-1){
int x = 0;
for(int j=0;j<8;j++){
if(decode_bit()){
x += 1<<j;
}
}
ternary.push_back(x/81);
ternary.push_back((x/27)%3);
ternary.push_back((x/9)%3);
ternary.push_back((x/3)%3);
ternary.push_back(x%3);
}
for(int j=1;j<n;j++){
dist[q[j]] = ternary[j-1]+dist[parent[q[j]]]-1;
}
for(int j=0;j<n;j++){
hops(i,j,dist[j]);
}
}
}