제출 #395052

#제출 시각아이디문제언어결과실행 시간메모리
395052MarcoMeijer저장 (Saveit) (IOI10_saveit)C++14
0 / 100
328 ms10724 KiB
#include "grader.h" #include "encoder.h" #include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e9 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second void writeSmallInt(int x, int bits) { RE(i,bits) { bool b = false; if(x & (1<<i)) b = 1; encode_bit(b); } } void encode(int nv, int nh, int ne, int *v1, int *v2) { // create original graph vector<vi> adj; adj.resize(nv); RE(i,ne) { adj[v1[i]].pb(v2[i]); adj[v2[i]].pb(v1[i]); } // spanning tree vector<vi> chl; chl.resize(nv); vi parent; parent.assign(nv, -1); // fill dist vector<vi> dist; dist.resize(nh); RE(h,nh) { dist[h].assign(nv,-1); queue<int> q; q.push(h); dist[h][h] = 0; while(!q.empty()) { int u = q.front(); q.pop(); FOR(v,adj[u]) { if(dist[h][v] != -1) continue; dist[h][v] = dist[h][u] + 1; q.push(v); if(h == 0) chl[u].pb(v), parent[v] = u; // create spanning tree } } } // functions int curH = 0; function<void(int)> writeSpan = [&](int u) { FOR(v,chl[u]) { encode_bit(1); writeSmallInt(v,10); writeSpan(v); } encode_bit(0); }; function<void(int)> writeDist = [&](int u) { if(parent[u] != -1) writeSmallInt(dist[curH][parent[u]] - dist[curH][u] + 1, 2); FOR(v,chl[u]) writeDist(v); }; // calling the above functions writeSpan(0); REP(h,1,nh) { curH = h; writeDist(0); } }
#include "grader.h" #include "decoder.h" #include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e9 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second int readSmallInt(int bits) { int res = 0; RE(i,bits) { bool b = decode_bit(); if(b) res |= (1<<i); } return res; } void decode(int nv, int nh) { // spanning tree vector<vi> chl; chl.resize(nv); vi parent; parent.assign(nv, -1); // distance array vector<vi> dist; dist.assign(nh, vi(nv,0)); // functions int curH = 0; function<void(int)> readSpan = [&](int u) { while(true) { bool b = decode_bit(); if(!b) return; int v = readSmallInt(10); chl[u].pb(v); readSpan(v); } }; function<void(int)> readDist = [&](int u) { if(parent[u] != -1) { int dif = readSmallInt(2) - 1; dist[curH][u] = dist[curH][parent[u]] + dif; } FOR(v,chl[u]) readDist(v); }; // calling the above functions readSpan(0); REP(h,1,nh) { curH = h; readDist(0); int delta = -dist[h][h]; RE(u,nv) dist[h][u] += delta; } // returning the answer RE(i,nh) RE(j,nv) hops(i,j,dist[i][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...