oj.uz

Submission #319577

# Submission time Handle Problem Language Result Execution time Memory
319577 2020-11-05T14:35:15 Z VEGAnn Fun Tour (APIO20_fun) C++14
21 / 100
 522 ms 97776 KB 
#include "fun.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 100100;
vector<int> g[N], ans;
set<int> elms[N];
int siz[N], glob, mx;
bool mrk[N];

void dfs(int v, int p, int len){
    if (mx < len){
        mx = len;
        glob = v;
    }

    for (int u : g[v]){
        if (u == p || mrk[u]) continue;

        dfs(u, v, len + 1);
    }
}

void add(int v){
    for (int u : g[v])
        add(u);

    int mem = v;

    while (1){
        elms[v].insert(mem);

        if (v == 0) break;

        v = ((v - 1) >> 1);
    }
}

void delt(int v){
    int mem = v;

    while (1){
        elms[v].erase(mem);

        if (v == 0) break;

        v = ((v - 1) >> 1);
    }
}

int get_len(int v, int p){
    int len = 0;
    while (v != p){
        len++;
        v = ((v - 1) >> 1);
    }
    return len;
}

vector<int> createFunTour(int n, int Q) {
//    if (n <= 500){
//        for (int i = 0; i < n; i++)
//        for (int j = i + 1; j < n; j++){
//            int now = hoursRequired(i, j);
//
//            if (now == 1){
//                g[i].PB(j);
//                g[j].PB(i);
//            }
//        }
//    } else
    {
//        if (n < 10) while (1) {}

        for (int i = 1; i < n; i++){
            int j = (i - 1) / 2;

//            g[i].PB(j);
            g[j].PB(i);
        }

        add(0);

        int rem = n, now = n - 1;

        while (1){
            ans.PB(now);
            rem--;
            mrk[now] = 1;

            delt(now);

            if (rem == 0) break;

            int mx = -1, who = -1;

            int cur = now, len = 0, pre = -1;

            if (sz(elms[cur]) > 0){
                int vl = (*(--elms[cur].end()));

                int upd = len + get_len(vl, cur);

                if (upd > mx){
                    mx = upd;
                    who = vl;
                }
            }

            while (1){
                if (cur == 0) break;

                pre = cur;
                cur = ((cur - 1) >> 1);
                len++;

                if (!mrk[cur]) {
                    if (mx < len){
                        mx = len;
                        who = cur;
                    }
                }

                for (int u : g[cur]){
                    if (u == pre) continue;

                    if (mrk[u] || sz(elms[u]) == 0) continue;

                    int vl = (*(--elms[u].end()));

                    int upd = len + get_len(vl, cur);

                    if (upd > mx){
                        mx = upd;
                        who = vl;
                    }
                }
            }

            assert(who >= 0);

            now = who;
        }

        return ans;
    }

    ans.clear();

    mx = -1;

    dfs(0, -1, 0);

    for (int it = 0; it < n; it++){
        ans.PB(glob);
        mrk[glob] = 1;

        mx = -1;

        dfs(glob, -1, 0);
    }

    return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7404 KB Tour is not fun

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7404 KB Tour is not fun

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7308 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7416 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 5 ms 7404 KB Output is correct
7 Correct 5 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 5 ms 7532 KB Output is correct
10 Correct 5 ms 7400 KB Output is correct
11 Correct 5 ms 7532 KB Output is correct
12 Correct 6 ms 7660 KB Output is correct
13 Correct 5 ms 7436 KB Output is correct
14 Correct 5 ms 7404 KB Output is correct
15 Correct 5 ms 7404 KB Output is correct
16 Correct 6 ms 7680 KB Output is correct
17 Correct 6 ms 7660 KB Output is correct
18 Correct 522 ms 97776 KB Output is correct
19 Correct 7 ms 7916 KB Output is correct
20 Correct 11 ms 8556 KB Output is correct
21 Correct 14 ms 9324 KB Output is correct
22 Correct 30 ms 12396 KB Output is correct
23 Correct 58 ms 17764 KB Output is correct
24 Correct 81 ms 21476 KB Output is correct
25 Correct 290 ms 58216 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7308 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Incorrect 5 ms 7404 KB Tour is not fun
5 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7404 KB Tour is not fun