이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |