Submission #436293

#	Time	Username	Problem	Language	Result	Execution time	Memory
436293		AmineTrabelsi	Fun Tour (APIO20_fun)	C++14	0 / 100	7 ms	7372 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 +5;
vector<int> tr[M];
int dist[M];
void cnt(int node,int par){
  for(auto i:tr[node]){
    if(i != par){
      dist[i] = dist[node]+1;
      cnt(i,node);
    }
  }
}
vector<int> nxt[M],nxt2[M];
vector<int> createFunTour(int N, int Q) {
  /*
  int H = hoursRequired(0, N - 1);
  int A = attractionsBehind(0, N - 1);
  */
  for(int i=1;i<N;i++){
    int s = (i-1)/2;
    tr[s].push_back(i);
    tr[i].push_back(s);
  }
  cnt(0,-1);
  int st = 0,mx = 0;
  for(int i=1;i<N;i++){
    int q = dist[i];
    if(q > mx){
      st = i;
      mx = q;
    }
  }
  dist[st] = 0;
  cnt(st,-1);
  for(int i=0;i<N;i++){
    nxt[dist[i]].push_back(i);
  }
  int en = 0;
  mx = 0;
  for(int i=1;i<N;i++){
    int q = dist[i];
    if(q > mx){
      en = i;
      mx = q;
    }
  }
  dist[en] = 0;
  cnt(en,-1);
  for(int i=0;i<N;i++){
    nxt2[dist[i]].push_back(i);
  }
  vector<int> f,s;
  for(int i=N-1;i>=0;i--){
    sort(nxt[i].rbegin(),nxt[i].rend());
    for(auto x:nxt[i]){
      f.push_back(x);
    }
    sort(nxt2[i].rbegin(),nxt2[i].rend());
    for(auto x:nxt2[i])s.push_back(x);

  }
/*
  for(auto i:f)cout << i<<" ";
    cout <<'\n';
  for(auto i:s)cout<<i<<" ";
    cout << '\n';
    */
  vector<bool> vis(N+1,0);
  vector<int> res;
  int pp = 0;
  for(int p=0;p<(int)s.size();p++){
    if(vis[s[p]])continue;
    while(vis[f[pp]])pp++;
    if(f[pp] == s[p])continue;
    vis[f[pp]] = 1;
    vis[s[p]] = 1;
    res.push_back(f[pp]);
    res.push_back(s[p]);
  }
  for(int i=0;i<N;i++){
    if(!vis[i])res.push_back(i); // hahahahah
  }
  /*
  for(auto i:res)cout<<i<<" ";
    cout<<'\n';
    */
  return res;
}

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