oj.uz

Submission #319456

# Submission time Handle Problem Language Result Execution time Memory
319456 2020-11-05T10:40:33 Z VEGAnn Fun Tour (APIO20_fun) C++14
0 / 100
 6 ms 5228 KB 
#include "fun.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
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) {
    assert(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);
        }
    }

    ans.clear();

    build_sz(0, -1);

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

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

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

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

    for (int it = 0; it < sz(g[cen]); it++)
        if (vc[it].back()[0] > mx){
            mx = 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 (vc[it].back()[0] > nw_mx){
                nw_mx = 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5228 KB Execution killed with signal 6 (could be triggered by violating memory limits)

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5228 KB Execution killed with signal 6 (could be triggered by violating memory limits)

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Runtime error 6 ms 5228 KB Execution killed with signal 6 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Runtime error 6 ms 5228 KB Execution killed with signal 6 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5228 KB Execution killed with signal 6 (could be triggered by violating memory limits)