Submission #319469

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
319469	2020-11-05T10:53:22 Z	VEGAnn	Fun Tour (APIO20_fun)	C++14	10 / 100	12 ms	2924 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;
vector<i2> vc[3];
int siz[N];

void build_sz(int v, int p){
    siz[v] = 1;

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

        build_sz(u, v);

        siz[v] += siz[u];
    }
}

int search(int v, int p, int SZ){
    for (int u : g[v]){
        if (u == p) continue;

        if (siz[u] > SZ / 2)
            return search(u, v, SZ);
    }
    return v;
}

void dfs(int v, int p, int ht, int tp){
    vc[tp].PB({ht, v});

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

        dfs(u, v, ht + 1, tp);
    }
}

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 {
        for (int i = 1; i < n; i++){
            int j = (i - 1) / 2;

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

    ans.clear();

    build_sz(0, -1);

    int cen = search(0, -1, siz[0]);

    assert(sz(g[cen]) < 4);

    for (int it = 0; it < sz(g[cen]); it++) {
        dfs(g[cen][it], cen, 1, it);

        sort(all(vc[it]));
    }

    int mx = -1, who = -1, tp = -1, bst = -1;

    for (int it = 0; it < sz(g[cen]); it++)
        if (sz(vc[it]) > mx || (sz(vc[it]) == mx && vc[it].back()[0] > bst)){
            mx = sz(vc[it]);
            bst = vc[it].back()[0];
            who = vc[it].back()[1];
            tp = it;
        }

    vc[tp].pop_back();
    ans.PB(who);

    for (int itr = 2; itr < n; itr++){
        int nw_mx = -1, nw = -1, wh = -1;

        for (int it = 0; it < sz(g[cen]); it++){
            if (it == tp || sz(vc[it]) == 0) continue;

            if (sz(vc[it]) > nw_mx || (sz(vc[it]) == mx && vc[it].back()[0] > bst)){
                nw_mx = sz(vc[it]);
                bst = vc[it].back()[0];
                nw = vc[it].back()[1];
                wh = it;
            }
        }

        assert(wh >= 0);

        vc[wh].pop_back();
        ans.PB(nw);

        tp = wh;
        who = nw;
    }

    ans.PB(cen);

    return ans;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	2 ms	2816 KB	Output is correct
3	Correct	3 ms	2668 KB	Output is correct
4	Correct	2 ms	2668 KB	Output is correct
5	Correct	2 ms	2668 KB	Output is correct
6	Correct	2 ms	2668 KB	Output is correct
7	Correct	2 ms	2668 KB	Output is correct
8	Correct	2 ms	2668 KB	Output is correct
9	Correct	2 ms	2668 KB	Output is correct
10	Correct	2 ms	2668 KB	Output is correct
11	Correct	2 ms	2668 KB	Output is correct
12	Correct	2 ms	2668 KB	Output is correct
13	Correct	2 ms	2664 KB	Output is correct
14	Correct	2 ms	2668 KB	Output is correct
15	Correct	2 ms	2668 KB	Output is correct
16	Correct	2 ms	2668 KB	Output is correct
17	Correct	2 ms	2668 KB	Output is correct
18	Correct	2 ms	2780 KB	Output is correct
19	Correct	2 ms	2700 KB	Output is correct
20	Correct	2 ms	2668 KB	Output is correct

Subtask #2
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	2 ms	2816 KB	Output is correct
3	Correct	3 ms	2668 KB	Output is correct
4	Correct	2 ms	2668 KB	Output is correct
5	Correct	2 ms	2668 KB	Output is correct
6	Correct	2 ms	2668 KB	Output is correct
7	Correct	2 ms	2668 KB	Output is correct
8	Correct	2 ms	2668 KB	Output is correct
9	Correct	2 ms	2668 KB	Output is correct
10	Correct	2 ms	2668 KB	Output is correct
11	Correct	2 ms	2668 KB	Output is correct
12	Correct	2 ms	2668 KB	Output is correct
13	Correct	2 ms	2664 KB	Output is correct
14	Correct	2 ms	2668 KB	Output is correct
15	Correct	2 ms	2668 KB	Output is correct
16	Correct	2 ms	2668 KB	Output is correct
17	Correct	2 ms	2668 KB	Output is correct
18	Correct	2 ms	2780 KB	Output is correct
19	Correct	2 ms	2700 KB	Output is correct
20	Correct	2 ms	2668 KB	Output is correct
21	Correct	3 ms	2800 KB	Output is correct
22	Correct	2 ms	2688 KB	Output is correct
23	Correct	2 ms	2668 KB	Output is correct
24	Incorrect	11 ms	2880 KB	Tour is not fun
25	Halted	0 ms	0 KB	-

Subtask #3
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2816 KB	Output is correct
2	Correct	3 ms	2668 KB	Output is correct
3	Correct	2 ms	2668 KB	Output is correct
4	Correct	2 ms	2668 KB	Output is correct
5	Correct	2 ms	2668 KB	Output is correct
6	Correct	2 ms	2668 KB	Output is correct
7	Correct	2 ms	2668 KB	Output is correct
8	Correct	2 ms	2668 KB	Output is correct
9	Correct	3 ms	2800 KB	Output is correct
10	Correct	2 ms	2688 KB	Output is correct
11	Correct	2 ms	2668 KB	Output is correct
12	Incorrect	11 ms	2880 KB	Tour is not fun
13	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2816 KB	Output is correct
2	Correct	3 ms	2668 KB	Output is correct
3	Correct	2 ms	2668 KB	Output is correct
4	Correct	2 ms	2668 KB	Output is correct
5	Correct	2 ms	2668 KB	Output is correct
6	Correct	2 ms	2664 KB	Output is correct
7	Correct	2 ms	2668 KB	Output is correct
8	Incorrect	12 ms	2924 KB	Tour is not fun
9	Halted	0 ms	0 KB	-

Subtask #5
0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	2 ms	2816 KB	Output is correct
3	Correct	3 ms	2668 KB	Output is correct
4	Correct	2 ms	2668 KB	Output is correct
5	Correct	2 ms	2668 KB	Output is correct
6	Correct	2 ms	2668 KB	Output is correct
7	Correct	2 ms	2668 KB	Output is correct
8	Correct	2 ms	2668 KB	Output is correct
9	Correct	2 ms	2668 KB	Output is correct
10	Correct	2 ms	2668 KB	Output is correct
11	Correct	2 ms	2668 KB	Output is correct
12	Correct	2 ms	2668 KB	Output is correct
13	Correct	2 ms	2664 KB	Output is correct
14	Correct	2 ms	2668 KB	Output is correct
15	Correct	2 ms	2668 KB	Output is correct
16	Correct	2 ms	2668 KB	Output is correct
17	Correct	2 ms	2668 KB	Output is correct
18	Correct	2 ms	2780 KB	Output is correct
19	Correct	2 ms	2700 KB	Output is correct
20	Correct	2 ms	2668 KB	Output is correct
21	Correct	3 ms	2800 KB	Output is correct
22	Correct	2 ms	2688 KB	Output is correct
23	Correct	2 ms	2668 KB	Output is correct
24	Incorrect	11 ms	2880 KB	Tour is not fun
25	Halted	0 ms	0 KB	-

Submission #319469

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0 / 16.0

Subtask #3 0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 34.0

Subtask #1
10.0 / 10.0

Subtask #2
0 / 16.0

Subtask #3
0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 34.0