| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 981603 | Marcus | Fun Tour (APIO20_fun) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
//const int N1 = 1e5;
//int n, q;
//vector<vector<int>> adj(N1);
//vector<int> traversal;
//vector<int> depth;
//vector<int> ind(N1);
//void LCM(int s, int v, int d)
//{
// ind[s] = (int)traversal.size();
// traversal.push_back(s);
// depth.push_back(d);
//
// for (auto u: adj[s])
// {
// if (u == v) continue;
// LCM(u, s, d+1);
// traversal.push_back(s);
// depth.push_back(d);
// }
//}
//
//struct SegmentTree {
// vector<pair<int, int>> t;
//
// SegmentTree(int power) : t(power) {}
//
// pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
// if (a.first < b.first) return a;
// else return b;
// }
//
// void build(vector<int>& a, int v, int tl, int tr) {
// if (tl == tr) {
// if (tl < (int)a.size()) t[tl] = {depth[tl], a[tl]};
// else t[tl] = {N1+1, N1+1};
// } else {
// int tm = (tl + tr) / 2;
// build(a, v*2, tl, tm);
// build(a, v*2+1, tm+1, tr);
// t[v] = combine(t[v*2], t[v*2+1]);
// }
// }
//
// pair<int, int> query(int v, int tl, int tr, int l, int r) {
// if (l > r) return make_pair(N1+1, N1+1);
// if (l == tl && r == tr) return t[v];
// int tm = (tl + tr) / 2;
// return combine(query(v*2, tl, tm, l, min(r, tm)),
// query(v*2+1, tm+1, tr, max(l, tm+1), r));
// }
//};
//
//vector<int> parent(N1);
//void dfs(int s, int v)
//{
// parent[s] = v;
// for (auto u: adj[s])
// {
// if (u == v) continue;
// dfs(u, s);
// }
//}
std::vector<int> createFunTour(int N, int Q) {
//n = N; q = Q;
//queue<int> que;
//int start = 0;
//que.push(start);
//vector<int> leave;
//while (!que.empty()) {
// int s = que.front(); que.pop();
// for (int i=0; i<n; i++)
// {
// int h = hoursRequired(s, i);
// if (h == 1) {adj[s].push_back(i); adj[i].push_back(s);}
// }
// if ((int)adj[s].size() == 1) {leave.push_back(s);}
// for (auto u : adj[s])
// {
// que.push(u);
// }
//}
vector<int> answer;
//if ((int)leave.size() == 2) {for (int i=0; i<n; i++) {answer.push_back(i);}}
//return answer;
//
//LCM(0, -1, 1);
//
//int volume = (int)traversal.size();
//int powtwo = __lg(volume) + !!(volume & (volume-1));
//SegmentTree segtree(powtwo); segtree.build(traversal, 1, 0, powtwo-1);
//int central = segtree.query(1, 0, powtwo-1, ind[leave[0]], ind[leave[1]]).second;
//
//vector<int> processing;
//tuple<int, int, int> prepath = {0, -1, -1};
//tuple<int, int, int> currpath = {0, -1, -1};
//vector<bool> visited(n);
//for (auto u: leave) {processing.push_back(u);}
//
//for (auto u: processing)
//{
// for (auto v: processing)
// {
// int h = hoursRequired(u, v);
// if (h > get<0>(prepath)) prepath = {h, u, v};
// }
//}
//visited[get<1>(prepath)] = true;
//visited[get<2>(prepath)] = true;
//processing.erase(find(processing.begin(), processing.end(), get<1>(prepath)));
//processing.erase(find(processing.begin(), processing.end(), get<1>(prepath)));
//
//
//while (!processing.empty()) {
// int u = get<1>(prepath);
// int v = get<2>(prepath);
// for (auto s: processing) {
// if (visited[s]) continue;
// int h = hoursRequired(u, s);
// if (h > get<0>(currpath)) currpath = {h, u, s};
// }
// for (auto s: processing) {
// if (visited[s]) continue;
// int h = hoursRequired(v, s);
// if (h > get<0>(currpath)) currpath = {h, v, s};
// }
// int s = get<2>(currpath);
// if (get<1>(currpath) == u) {answer.push_back(v); answer.push_back(u); answer.push_back(s);}
// else {answer.push_back(u); answer.push_back(v); answer.push_back(s);}
// visited[u] = visited[v] = visited[s] = true;
// if (parent[s] != central) {processing.push_back(parent[s]);}
// processing.erase(find(processing.begin(), processing.end(), s));
//}
//answer.push_back(central);
for (int i=0; i<n; i++) {answer.push_back(i);}
return answer;
}