Submission #1226877

#TimeUsernameProblemLanguageResultExecution timeMemory
1226877TrumlingSaveit (IOI10_saveit)C++20
50 / 100
784 ms16648 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; 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>()); 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) tree[curr].pb(x); q.push(x); dist[i][x]=dist[i][curr]+1; vis[x]=1; } } } queue<ll>q; q.push(0); ll left=n-1; set<ll>s; for(int i=1;i<n;i++) s.insert(i); while(!q.empty()) { ll curr=q.front(); q.pop(); for(auto x:tree[curr]) { encode_bit(1); ll idx=0; for(auto itr=s.begin();itr!=s.end();itr++) { if(*itr==x) break; idx++; } ll temp=idx; ll l=0; while((1<<l)<=left) l++; left--; s.erase(x); for(int i=0;i<l;i++) { encode_bit(temp%2); temp/=2; } q.push(x); } encode_bit(0); } for(int i=0;i<h;i++) { q.push(0); while(!q.empty()) { ll curr=q.front(); q.pop(); for(auto x:tree[curr]) { if(dist[i][curr] < dist[i][x]) { encode_bit(1); encode_bit(1); } if(dist[i][curr] == dist[i][x]) { encode_bit(0); encode_bit(0); } if(dist[i][curr] > dist[i][x]) { encode_bit(0); encode_bit(1); } q.push(x); } } } 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,-1); queue<ll>q; q.push(0); ll left=n-1; set<ll>s; for(int i=1;i<n;i++) s.insert(i); while(!q.empty()) { ll get=decode_bit(); if(get==0) q.pop(); else { ll curr=0; ll l=0; while((1<<l)<=left) l++; left--; for(int j=0;j<l;j++) if(decode_bit()) curr+=(1<<j); ll idx=0; for(auto itr=s.begin();itr!=s.end();itr++) { if(idx==curr) { curr=*itr; break; } idx++; } tree[q.front()].pb(curr); par[curr]=q.front(); q.push(curr); s.erase(curr); } } vector<vector<ll>>p(n,vector<ll>(n,0)); for(int i=0;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]) { ll id=2*decode_bit() + decode_bit(); if(id==0) { p[curr][x]=0; p[x][curr]=0; } if(id==1) { 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]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...