oj.uz

Submission #982978

# Submission time Handle Problem Language Result Execution time Memory
982978 2024-05-15T06:22:54 Z ZHIRDILBILDIZ Fun Tour (APIO20_fun) C++14
26 / 100
 9 ms 1460 KB 
#include <bits/stdc++.h>
#include "fun.h"
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>

using namespace std;
const int N = 1e5 + 10;

// int ind[N];
// int ds[N];
// int pw[2 * N];
// pii mn[2 * N][20];

// vector<pii> tr;
// vector<int> gr[N];
// void dfs (int city, int pr) {
//     ind[city] = tr.size();
//     tr.push_back({ds[city], city});
//     for (int i : gr[city]) {
//         if (i == pr)
//             continue;
//         ds[i] = ds[city] + 1;
//         dfs(i, city);
//         tr.push_back({ds[city], city});
//     }
// }

// void build_sparce () {
//     for (int i = 2; i <= tr.size(); ++i)
//         pw[i] = pw[i >> 1] + 1;
//     for (int i = 0; i < tr.size(); ++i)
//         mn[i][0] = tr[i];
//     for (int i = 1; i < 20; ++i)
//         for (int j = 0; j <= (int)tr.size() - (1 << i); ++j)
//             mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
// }
// int get_lca (int u, int v) {
//     u = ind[u];
//     v = ind[v];
//     if (u > v)
//         swap(u, v);
//     int x = pw[v - u + 1];
//     return min(mn[u][x], mn[v - (1 << x) + 1][x]).se;
// }
// int get_dist (int u, int v) {
//     int lc = get_lca(u, v);
//     return dist[u] + dist[v] - dist[lc] * 2;
// }
// int hoursRequired (int u, int v) {
//     cout << "? " << u << ' ' << v << '\n';
//     int x = get_dist(u, v);
//     return x;
// }
// int attractionsBehind () {
// }

vector<int> createFunTour (int n, int q) {
    vector<int> res;
    if (n <= 500) {
        int dist[n][n];
        int mx = 0;
        pii fr;

        for (int i = 0; i < n; ++i) {
            dist[i][i] = 0;
            for (int j = i + 1; j < n; ++j) {
                if (i != j) {
                    int w = hoursRequired(i, j);
                    dist[i][j] = w;
                    dist[j][i] = w;
                }
                mx = max(mx, dist[i][j]);
                if (mx == dist[i][j])
                    fr = {i, j};
            }
        }
        bool us[n] = {};
        us[fr.fi] = 1;
        res.push_back(fr.fi);
        us[fr.se] = 1;
        res.push_back(fr.se);
        
        int city = fr.se;
        for (int i = 3; i <= n; ++i) {
            int loc_mx = 0;
            int who = -1;
            for (int j = 0; j < n; ++j) {
                if (us[j])
                    continue;
                loc_mx = max(loc_mx, dist[city][j]);
                if (loc_mx == dist[city][j])
                    who = j;
            }
            us[who] = 1;
            res.push_back(who);
            city = who;
        }
    }
    return res;
}

// signed main () {

//     int n, q;
//     cin >> n >> q;
//     for (int i = 1; i < n; ++i) {
//         int u, v;
//         cin >> u >> v;
//         gr[u].push_back(v);
//         gr[v].push_back(u);
//     }

//     dfs(0, -1);
//     build_sparce();

//     vector<int> ans = createFunTour(n, q);
//     for (int i : ans)
//         cout << i << ' ';
//     cout << '\n';

//     return 0;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 356 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 432 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 356 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 432 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 8 ms 1372 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 436 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 8 ms 1372 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 4 ms 756 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 8 ms 1460 KB Output is correct
35 Correct 9 ms 1372 KB Output is correct
36 Correct 9 ms 1372 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 9 ms 1316 KB Output is correct
39 Correct 3 ms 600 KB Output is correct
40 Correct 5 ms 936 KB Output is correct
41 Correct 2 ms 344 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 8 ms 1372 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Incorrect 1 ms 348 KB Invalid size
17 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 8 ms 1372 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 4 ms 756 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Incorrect 1 ms 348 KB Invalid size
14 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 356 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 432 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 8 ms 1372 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 436 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 8 ms 1372 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 4 ms 756 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 8 ms 1460 KB Output is correct
35 Correct 9 ms 1372 KB Output is correct
36 Correct 9 ms 1372 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 9 ms 1316 KB Output is correct
39 Correct 3 ms 600 KB Output is correct
40 Correct 5 ms 936 KB Output is correct
41 Correct 2 ms 344 KB Output is correct
42 Incorrect 1 ms 348 KB Invalid size
43 Halted 0 ms 0 KB -