Submission #612603

#	Time	Username	Problem	Language	Result	Execution time	Memory
612603		AugustinasJucas	Fun Tour (APIO20_fun)	C++14	47 / 100	136 ms	24256 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;

const int dydis = 1e5 + 10;

vector<int> gr[dydis];
int n;
bool rem[dydis] = {};
int dst[dydis] = {};
void dfs(int v, int came) {
    if(rem[v]) return;

    for(auto x : gr[v]) {
        if(x == came) continue;
        dst[x] = dst[v] + 1;
        ////cout << "dst[" << v << "] = " << dst[v] << ", tai dst[" << x << "] = " << dst[x] << endl;
        dfs(x, v);
    }
}
int furthest (int a) {
   // //cout << "ieskau atstumu nuo " << a << endl;
    dst[a] = 0;
    dfs(a, -1);
    int mx = 0; int sk = a;
    for(int i = 0; i < n; i++) {
        if(rem[i]) continue;
  //      //cout << "dst[" << i << "] = " << dst[i] << endl;
        if(dst[i] > mx) {
            mx = dst[i];
            sk = i;
        }
    }
    return sk;
}
vector<int> nMazas(){

    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            if(hoursRequired(i, j) == 1) {
                gr[i].push_back(j);
                gr[j].push_back(i);
            }
        }
    }

    vector<int> ret;
    int v = furthest(0);
    for(int i = 0; i < n; i++) {
       // //cout << "i = " << i << ", v = " << v << endl;
        ret.push_back(v);
        int was = v;
        v = furthest(v);
        rem[was] = 1;
     //   //cout << endl;
    }

    return ret;
}

pair<int, int> toliausia[dydis];

void d(int v, int came) {
    if(rem[v]) return ;
    toliausia[v] = {-1, v};
    for(auto x : gr[v]) {
        if(x == came) continue;
        d(x, v);
        toliausia[v] = max(toliausia[v], toliausia[x]);
    }
    toliausia[v].first++;
}

void remN(int v){

    int in = v;
    while(!rem[v]) {
        toliausia[v] = {0, v};
        if(v == in) toliausia[v] = {-1, -1};
        for(auto x : gr[v]) {
            if(x < v) continue;
            if(rem[x]) continue;
            toliausia[v] = max(toliausia[v], make_pair(toliausia[x].first+1, toliausia[x].second));
        }
        if(v == 0) break ;
        v = (v - 1) / 2;
    }
     rem[in] = 1;
    //cout << "isemus " << in << ", toliausios: \n";
    for(int i = 0; i < n; i++) {
        //cout << i << "-ajai toliausia yra " << toliausia[i].second << ", ds = "<< toliausia[i].first << endl;
    }
}

int findFar(int v) {
    pair<int, int> ret = toliausia[v];
    int init = v;
    int ds = 1;
    int V = v;
    //cout << "findfar nuo " << v << endl;
    while(true) {
        for(auto x : gr[v]) {
            if(x == init || x < v) continue;
            if(rem[x]) continue;
            //cout << "v = " << v << ", x = " << x <<", tai dst gali buti " << toliausia[x].first + ds<< endl;
            ret = max(ret, make_pair(toliausia[x].first + ds, toliausia[x].second));
        }
        if(rem[v] || v == 0) break;
        init = v;
        v = (v - 1) / 2;
        ds++;
    }
    return ret.second;
}

vector<int> createFunTour(int N, int Q) {

    n = N;if(n <= 500) return nMazas();
  //  //cout << "a" << endl;
 //   if(n <= 500) return nMazas();
    for(int i = 1; i < n; i++) {
        int pr = (i-1) / 2;
        gr[pr].push_back(i);
        gr[i].push_back(pr);
    }
    ////cout << "x" << endl;
    d(0, -1);
  //  //cout << "don" << endl;
    int v = toliausia[0].second;
    set<int> nodes;
    for(int i = 0; i < n; i++) nodes.insert(i);
    vector<int> ret;
    int root = 0;
    for(int i = 0; i < n-2; i++) {
        int was = v;
        v = findFar(v);
        //cout << "toliausia nuo " << was << " yra " << v << endl;
        remN(was);
        ret.push_back(was);
        nodes.erase(was);

    }
    ret.push_back(*nodes.begin());
    nodes.erase(*nodes.begin());
    ret.push_back(*nodes.begin());
    //cout << "ret: "; for(auto x : ret) //cout << x <<" "; //cout << endl;
    return ret;
}

Compilation message (stderr)

fun.cpp: In function 'int findFar(int)':
fun.cpp:99:9: warning: unused variable 'V' [-Wunused-variable]
   99 |     int V = v;
      |         ^
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:133:9: warning: unused variable 'root' [-Wunused-variable]
  133 |     int root = 0;
      |         ^~~~

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