| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 506159 | jerzyk | 저장 (Saveit) (IOI10_saveit) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1000 + 7;
vector<int>ed[N];
int tab[38][1000 + 7], wsk[N];
ll Return3(int v, int h)
{
ll w, m;
for(int i = 1; i <= h; ++i)
{
if(tab[i][v] == tab[i][wsk[i]])
m = 1;
if(tab[i][v] > tab[i][wsk[i]])
m = 2;
w += m * pow(3LL, (ll)i - 1);
}
return w;
}
void PrintBits(ll x, int l)
{
for(int i = 1; i <= l; ++i)
{
encode_bit(x % 2);
x /= 2;
}
}
void DFS(int v)
{
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(wsk[ed[v][i]] == 0)
{
wsk[ed[v][i]] = v;
DFS(ed[v][i]);
}
}
}
void BFS(int n, int s)
{
int v;
queue<int> q;
for(int i = 1; i <= n; ++i)
tab[s][i] = N * 2;
tab[s][s] = 0;
q.push(s);
while(q.size() > 0)
{
v = q.front();
q.pop();
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(tab[s][ed[v][i]] > tab[s][v] + 1)
{
tab[s][ed[v][i]] = tab[s][v] + 1;
q.push(ed[v][i]);
}
}
}
}
void encode(int n, int h, int m, int* a, int* b)
{
for(int i = 0; i < m; ++i)
{
ed[a[i] + 1].push_back(b[i] + 1);
ed[a[i] + 1].push_back(b[i] + 1);
}
for(int i = 1; i <= h; ++i)
BFS(n, i);
wsk[1] = 1;
DFS(1);
for(int i = 2; i <= h; ++i)
PrintBits(tab[i][1], 10);
for(int i = 2; i <= n; ++i)
{
PrintBits(wsk[i], 10);
PrintBits(Return3(i, h), 58);
}
}
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000 + 7;
int odl[37][N], dod[37][N], ws[N];
vector<int>ed[N];
void DFS(int v, int h)
{
for(int i = 1; i <= h; ++i)
odl[i][v] = dod[i][v] + odl[i][ws[v]];
for(int i = 0; i < (int)ed[v].size(); ++i)
DFS(ed[v][i]);
}
void Dod(ll l, int v, int h)
{
for(int i = 1; i <= h; ++i)
{
if(l % 3LL == 0)
dod[i][v] = -1;
if(l % 3LL == 2)
dod[i][v] = 1;
}
}
ll ReadBits(int n)
{
int b;
ll w = 0LL;
for(int i = 0; i < n; ++i)
{
b = decode_bit();
w += pow(2LL, j) * b;
}
return w;
}
void decode(int n, int h)
{
for(int i = 2; i <= h; ++i)
odl[i][1] = ReadBits(10);
for(int i = 2; i <= n; ++i)
{
ws[i] = ReadBits(10);
ed[ws[i]].push_back(i);
Dod(ReadBits(58), i, h);
}
DFS(1);
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= n; ++j)
hops(i - 1, j - 1, odl[i][j]);
}