| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1056942 | ssense | Floppy (RMI20_floppy) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include "floppy.h"
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>
#define fr first
#define sc second
using namespace std;
#define NMAX 100000
#define MMAX 100000
// int subtask_id, N, M;
// std::vector<int> v, sorted_v;
// std::vector<int> a, b;
// std::vector<int> correct_answers;
// // Print score to stdout and exit.
// void score_and_exit(const double pts, const char *verdict) {
// fprintf(stderr, "%s", verdict);
// fprintf(stdout, "%f", pts);
// exit(0);
// }
// // Contestant sent too many bits.
// void too_many_bits() {
// score_and_exit(0, "Too many stored bits!");
// }
// // Contestant did not send any bits.
// void misformatted_stored_bits() {
// score_and_exit(0, "Misformatted stored bits or save_to_floppy not called!");
// }
// // Contestant did not call the answer function.
// void answer_not_provided() {
// score_and_exit(0, "Answer not provided!");
// }
// // Contestant sent a wrong answer.
// void wrong_answer() {
// score_and_exit(0, "Wrong answer to query!");
// }
// // Contestant sent a correct answer.
// void correct_answer() {
// score_and_exit(1, "OK!");
// }
// void read_test() {
// assert(scanf("%d", &subtask_id) == 1);
// assert(scanf("%d%d", &N, &M) == 2);
// assert(1 <= N && N <= NMAX);
// assert(0 <= M && M <= MMAX);
// v.resize(N);
// for (int i = 0; i < N; ++i) {
// assert(scanf("%d", &v[i]) == 1);
// }
// // Check all values are distinct.
// sorted_v.resize(N);
// for (int i = 0; i < N; ++i) {
// sorted_v[i] = v[i];
// }
// std::sort(sorted_v.begin(), sorted_v.end());
// for (int i = 0; i + 1 < N; ++i) {
// assert(sorted_v[i] < sorted_v[i + 1]);
// }
// a.resize(M);
// b.resize(M);
// correct_answers.resize(M);
// for (int i = 0; i < M; ++i) {
// assert(scanf("%d%d%d", &a[i], &b[i], &correct_answers[i]) == 3);
// assert(0 <= a[i] && a[i] <= correct_answers[i] &&
// correct_answers[i] <= b[i] && b[i] < N);
// }
// }
int leftc[NMAX], rightc[NMAX];
int par[18][NMAX], depth[NMAX];
int timer = 0;
void dfs_1(int u, const string &bits)
{
if(bits[2*u] == '1')
{
int new_node = timer++;
par[0][new_node] = u;
leftc[u] = new_node;
depth[new_node] = depth[u]+1;
dfs_1(new_node, bits);
}
if(bits[2*u+1] == '1')
{
int new_node = timer++;
par[0][new_node] = u;
rightc[u] = new_node;
depth[new_node] = depth[u]+1;
dfs_1(new_node, bits);
}
}
int jump(int a, int l)
{
for(int i = 0; i < 18; i++)
{
if((l&(1<<i)) != 0)
{
a = par[i][a];
}
}
return a;
}
int lca(int a, int b)
{
if(depth[a] < depth[b])
{
swap(a, b);
}
a = jump(a, depth[a]-depth[b]);
if(a == b)
{
return a;
}
for(int i = 17; i >= 0; i--)
{
if(par[i][a] != par[i][b])
{
a = par[i][a];
b = par[i][b];
}
}
return par[0][a];
}
int trans[NMAX], inv_trans[NMAX];
int code = 0;
void dfs_2(int u)
{
if(leftc[u] != -1)
{
dfs_2(leftc[u]);
}
trans[u] = code;
inv_trans[code] = u;
code++;
if(rightc[u] != -1)
{
dfs_2(rightc[u]);
}
}
vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b)
{
for(int i = 0; i <= n; i++)
{
leftc[i] = -1;
rightc[i] = -1;
par[0][i] = -1;
}
dfs_1(0, bits);
for(int i = 1; i <= 17; i++)
{
for(int j = 0; j < n; j++)
{
p[i][j] = p[i-1][p[i-1][j]];
}
}
// cout << "DEPTH: " << endl;
// for(int i = 0; i < n; i++)
// {
// cout << depth[i] << " ";
// }
// cout << endl;
dfs_2(0);
// cout << "TRANS: " << endl;
// for(int i = 0; i < n; i++)
// {
// cout << trans[i] << " ";
// }
// cout << endl;
vector<int> answers;
// cout << "ANSWERS: " << endl;
for(int i = 0; i < a.size(); i++)
{
// cout << "A[i]: " << inv_trans[a[i]] << " B[i]: " << inv_trans[b[i]] << " LCA: " << lca(inv_trans[a[i]], inv_trans[b[i]]) << endl;
answers.push_back(trans[lca(inv_trans[a[i]], inv_trans[b[i]])]);
//cout << answers.back() << endl;
}
return answers;
}
// void save_to_floppy(const std::string &bits) {
// std::vector<int> contestant_answers = solve_queries(subtask_id, N, bits, a, b);
// for (int i = 0; i < M; ++i) {
// if (contestant_answers[i] != correct_answers[i]) {
// wrong_answer();
// }
// }
// correct_answer();
// exit(0);
// }
void read_array(int subtask_id, const vector<int> &v)
{
int n = v.size();
int rc[n], lc[n], p[n];
for(int i = 0; i < n; i++)
{
rc[i] = -1;
lc[i] = -1;
p[i] = -1;
}
int root = 0;
for(int i = 1; i < n; i++)
{
int last_val = i-1;
while(last_val != -1)
{
if(-v[last_val] < -v[i])
{
lc[i] = rc[last_val];
rc[last_val] = i;
p[i] = last_val;
p[lc[i]] = i;
break;
}
last_val = p[last_val];
}
if(last_val == -1)
{
lc[i] = root;
p[root] = i;
root = i;
}
}
string bits = "";
stack<int> s;
s.push(root);
while(!s.empty())
{
int nw = s.top();
s.pop();
string bruh = "00";
if(rc[nw] != -1)
{
bruh[1] = '1';
s.push(rc[nw]);
}
if(lc[nw] != -1)
{
bruh[0] = '1';
s.push(lc[nw]);
}
bits+=bruh;
}
// cout << bits << endl;
save_to_floppy(bits);
}
// int main(int argc, char **argv) {
// // Read input data.
// read_test();
// // Send subtask_id, v.
// read_array(subtask_id, v);
// answer_not_provided();
// return 0;
// }
/*
3
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3
*/
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/