제출 #1202720

#제출 시각아이디문제언어결과실행 시간메모리
1202720a.pendovSaveit (IOI10_saveit)C++20
100 / 100
48 ms5956 KiB
#include <bits/stdc++.h> #include "grader.h" #include "encoder.h" using namespace std; const long long MAXN=1009; vector<int> edg[MAXN]; long long father[MAXN]; long long dist[MAXN]; long long code[MAXN]; long long vis[MAXN]; void pB(long long n,int bits) { for(int i=0;i<bits;i++)encode_bit(bool(n&(1LL<<i))); } void dfs(int a) { vis[a]=1; for(auto i:edg[a]) { if(vis[i])continue; father[i]=a; dfs(i); } } void bfs(int start) { memset(dist,-1,sizeof(dist)); dist[start]=0; queue<int> q; q.push(start); while(!q.empty()) { int curr=q.front(); q.pop(); for(auto i:edg[curr]) { if(dist[i]!=-1)continue; dist[i]=dist[curr]+1; q.push(i); } } } void encode(int nv, int nh, int ne, int *v1, int *v2) { memset(father,-1,sizeof(father)); for(int i=0;i<ne;i++) { edg[v1[i]].push_back(v2[i]); edg[v2[i]].push_back(v1[i]); } dfs(0); for(int i=0;i<nh;i++) { bfs(i); pB(dist[0],10); for(int j=1;j<nv;j++) { code[j]=code[j]*3+dist[father[j]]-dist[j]+1; } } for(int i=1;i<nv;i++) { pB(father[i],10); pB(code[i],58); } }
#include <bits/stdc++.h> #include "grader.h" #include "decoder.h" using namespace std; const long long MAXN1=1009; long long father1[MAXN1]; long long ans[MAXN1][40]; long long code1[MAXN1][40]; vector<bool> bt; long long f(int n,int h) { if(n==0)return ans[n][h]; if(ans[n][h]!=-1)return ans[n][h]; return ans[n][h]=f(father1[n],h)-code1[n][h]; } void decode(int nv, int nh) { for(int i=0;i<nh*10+(nv-1)*68;i++)bt.push_back(decode_bit()); memset(ans,-1,sizeof(ans)); for(int i=0;i<nh;i++) { for(int j=i*10;j<i*10+10;j++) { ans[0][i]+=(1LL<<(j-i*10))*bt[j]; } ++ans[0][i]; } long long x; for(int i=1;i<nv;i++) { x=0; for(int j=nh*10+(i-1)*68;j<nh*10+(i-1)*68+10;j++) { father1[i]+=(1LL<<(j-(nh*10+(i-1)*68)))*bt[j]; } for(int j=nh*10+(i-1)*68+10;j<nh*10+(i-1)*68+68;j++) { x+=(1LL<<(j-(nh*10+(i-1)*68+10)))*bt[j]; } for(int j=nh-1;j>=0;j--) { code1[i][j]=x%3-1; x/=3; } } for(int i=0;i<nh;i++) { for(int j=0;j<nv;j++) { hops(i,j,f(j,i)); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...