| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1224861 | boclobanchat | Saveit (IOI10_saveit) | C++20 | 0 ms | 0 KiB |
#include"grader.h"
#include"encoder.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
const int INF=1e9;
int dp[MAXN][MAXN],trace[MAXN][MAXN];
vector<int> ds[MAXN],vi[MAXN];
bool comp(pair<int,long long> a,pair<int,long long> b)
{
return __builtin_popcountll(a.second)>__builtin_popcountll(b.second);
}
void encode(int nv,int nh,int ne,int *v1,int *v2)
{
for(int i=0;i<ne;i++) ds[v1[i]].push_back(v2[i]),ds[v2[i]].push_back(v1[i]);
for(int i=0;i<nh;i++)
{
queue<int> Q;
for(int j=0;j<nv;j++) dp[i][j]=INF;
dp[i][i]=0,Q.push(i);
while(!Q.empty())
{
int a=Q.front();
Q.pop();
for(auto v:ds[a]) if(dp[i][v]==INF) dp[i][v]=dp[i][a]+1,Q.push(v);
}
}
for(int i=0;i<nv;i++)
{
vector< pair<int,long long> > vv;
for(auto v:ds[a])
{
long long mask=0;
for(int j=0;j<nh;j++) mask|=(1LL<<j)*(dp[j][i]==dp[j][v]+1);
vv.push_back({v,mask});
}
sort(vv.begin(),vv.end(),comp);
long long mask=0;
for(auto v:vv)
{
if((mask&v.second)==v.second) continue;
mask|=v.second,vi[i].push_back(v.first);
if(mask==(1LL<<(nh+1))-1) break;
}
}
for(int i=0;i<nv;i++)
{
sort(vi[i].begin(),vi[i].end());
vi[i].erase(unique(vi[i].begin(),vi[i].end()),vi[i].end());
int sz=vi[i].size();
for(int j=5;j+1;j--) encode_bit((sz>>j)%2);
for(auto v:vi[i]) for(int j=9;j+1;j--) encode_bit((v>>j)%2);
}
}
#include"grader.h"
#include"decoder.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
const int INF=1e9;
int dp[MAXN][MAXN],trace[MAXN][MAXN];
vector<int> ds[MAXN],vi[MAXN];
void decode(int nv,int nh)
{
for(int i=0;i<nv;i++)
{
int sz=0;
for(int j=5;j+1;j--) sz=sz*2+decode_bit();
while(sz--)
{
int res=0;
for(int j=9;j+1;j--) res=res*2+decode_bit();
ds[i].push_back(res),ds[res].push_back(i);
}
}
for(int i=0;i<nh;i++)
{
queue<int> Q;
for(int j=0;j<nv;j++) dp[i][j]=INF;
dp[i][i]=0,Q.push(i);
while(!Q.empty())
{
int a=Q.front();
Q.pop();
for(auto v:ds[a]) if(dp[i][v]==INF) dp[i][v]=dp[i][a]+1,trace[i][v]=a,Q.push(v);
}
for(int j=0;j<nv;j++) hops(i,j,dp[i][j]);
}
}