| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1228396 | Trumling | Saveit (IOI10_saveit) | C++20 | 0 ms | 0 KiB |
#include "grader.h"
#include "encoder.h"
//Trumling ©
//Αφόδευε υψηλά και ηγνάντει
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()
vector<vector<ll>>g;
vector<vector<ll>>dist;
vector<vector<ll>>tree;
vector<ll>par;
ll n,h,m;
void encode(int nv, int nh, int ne, int *v1, int *v2){
n=nv;
h=nh;
m=ne;
ll count=0;
g.assign(n,vector<ll>());
dist.assign(n,vector<ll>(n,INF));
tree.assign(n,vector<ll>());
par.assign(n,-1);
for(int i=0;i<m;i++)
{
g[v1[i]].pb(v2[i]);
g[v2[i]].pb(v1[i]);
}
for(int i=0;i<n;i++)
{
vector<bool>vis(n,0);
vis[i]=1;
queue<ll>q;
q.push(i);
dist[i][i]=0;
while(!q.empty())
{
ll curr=q.front();
q.pop();
for(auto x:g[curr])
if(!vis[x])
{
if(i==0)
{
par[x]=curr;
tree[curr]=x;
}
q.push(x);
dist[i][x]=dist[i][curr]+1;
vis[x]=1;
}
}
}
for(int i=1;i<n;i++)
{
ll temp=par[i];
for(int j=0;j<10;j++)
{
encode_bit(temp%2);
temp/=2;
}
}
for(int i=0;i<n;i++)
sort(all(tree[i]));
queue<ll>q;
for(int i=1;i<h;i++)
{
q.push(0);
while(!q.empty())
{
ll curr=q.front();
q.pop();
for(auto x:tree[curr])
{
count+=2;
if(dist[i][curr] < dist[i][x])
{
encode_bit(1);
encode_bit(1);
}
if(dist[i][curr] == dist[i][x])
{
encode_bit(0);
}
if(dist[i][curr] > dist[i][x])
{
encode_bit(1);
encode_bit(0);
}
q.push(x);
}
}
}
assert(count<81000);
return;
}
#include "grader.h"
#include "decoder.h"
//Trumling ©
//Αφόδευε υψηλά και ηγνάντει
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()
vector<vector<ll>>tree;
vector<ll>par;
ll n,h;
void decode(int nv, int nh) {
n=nv;
h=nh;
tree.assign(n,vector<ll>());
par.assign(n,0);
for(int i=1;i<n;i++)
{
for(int j=0;j<10;j++)
if(decode_bit())
par[i]+=(1<<j);
tree[par[i]].pb(i);
}
for(int i=0;i<n;i++)
sort(all(tree[i]));
queue<ll>q;
vector<vector<ll>>p(n,vector<ll>(n,0));
for(int i=1;i<h;i++)
{
vector<ll>dist(n,0);
q.push(0);
while(!q.empty())
{
ll curr=q.front();
q.pop();
for(auto x:tree[curr])
{
bool bit=decode_bit();
if(!bit)
{
p[curr][x]=0;
p[x][curr]=0;
}
else
{
ll id=2*x + decode_bit();
if(id==2)
{
p[curr][x]=-1;
p[x][curr]=1;
}
if(id==3)
{
p[curr][x]=1;
p[x][curr]=-1;
}
}
q.push(x);
}
}
ll now=i;
while(now!=0)
{
dist[par[now]]=dist[now]+p[now][par[now]];
now=par[now];
}
q.push(0);
while(!q.empty())
{
ll curr=q.front();
q.pop();
for(auto x:tree[curr])
{
dist[x] = dist[curr] + p[curr][x];
q.push(x);
}
}
for(int j=0;j<n;j++)
hops(i,j,dist[j]);
}
queue<pair<ll,ll>>q2;
q2.push({0,0});
hops(0,0,0);
while(!q2.empty())
{
pair<ll,ll>curr=q2.front();
q2.pop();
for(auto x:tree[curr.F])
{
q2.push({x,curr.S+1});
hops(0,x,curr.S+1);
}
}
}