Submission #981605

#	Time	Username	Problem	Language	Result	Execution time	Memory
981605		Marcus	Fun Tour (APIO20_fun)	C++17	0 / 100	2 ms	3164 KiB

fun

#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34