oj.uz

Submission #1049361

# Submission time Handle Problem Language Result Execution time Memory
1049361 2024-08-08T17:02:17 Z Zicrus Longest Trip (IOI23_longesttrip) C++17
15 / 100
 731 ms 1696 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
 
typedef long long ll;
 
vector<vector<ll>> adj, noAdj;
vector<bool> vst;
vector<vector<ll>> k;

void dfs(ll cur, ll comp) {
    vst[cur] = true;
    k[comp].push_back(cur);
    for (auto &e : noAdj[cur]) {
        if (vst[e]) continue;
        dfs(e, !comp);
    }
}
 
vector<int> longest_trip(int n, int d) {
    adj = vector<vector<ll>>(n);
    noAdj = vector<vector<ll>>(n);
    k = vector<vector<ll>>(2);
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (are_connected({i}, {j})) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
            else {
                noAdj[i].push_back(j);
                noAdj[j].push_back(i);
            }
        }
    }

    vst = vector<bool>(n);
    ll comp = 0;
    for (int i = 0; i < n; i++) {
        if (vst[i]) continue;
        dfs(i, 0);
        comp = !comp;
    }
    if (k[0].size() < k[1].size()) swap(k[0], k[1]);

    ll mxDeg = 0, bridge = 0;
    for (auto &e : k[0]) {
        if (adj[e].size() > mxDeg) {
            mxDeg = adj[e].size();
            bridge = e;
        }
    }

    vst = vector<bool>(n);
    vector<int> res;
    for (auto &e : k[0]) {
        vst[e] = true;
        if (e == bridge) continue;
        res.push_back(e);
    }
    res.push_back(bridge);
    ll used = -1;
    for (auto &e : adj[bridge]) {
        if (vst[e]) continue;
        res.push_back(used = e);
        break;
    }
    if (used == -1) return res;
    for (auto &e : k[1]) {
        if (e == used) continue;
        res.push_back(e);
    }

    return res;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:48:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   48 |         if (adj[e].size() > mxDeg) {
      |             ~~~~~~~~~~~~~~^~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 173 ms 1696 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 508 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 133 ms 460 KB Output is correct
4 Correct 340 ms 572 KB Output is correct
5 Correct 686 ms 1320 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 121 ms 456 KB Output is correct
4 Correct 312 ms 588 KB Output is correct
5 Correct 708 ms 1180 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Correct 123 ms 452 KB Output is correct
9 Correct 278 ms 856 KB Output is correct
10 Correct 706 ms 1236 KB Output is correct
11 Correct 722 ms 1308 KB Output is correct
12 Correct 699 ms 1160 KB Output is correct
13 Correct 690 ms 1380 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 120 ms 468 KB Output is correct
4 Correct 336 ms 784 KB Output is correct
5 Correct 691 ms 1220 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Correct 129 ms 684 KB Output is correct
9 Correct 251 ms 600 KB Output is correct
10 Correct 726 ms 1088 KB Output is correct
11 Correct 691 ms 1104 KB Output is correct
12 Correct 659 ms 1108 KB Output is correct
13 Correct 712 ms 1528 KB Output is correct
14 Correct 8 ms 340 KB Output is correct
15 Incorrect 2 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 13 ms 344 KB Output is correct
3 Partially correct 149 ms 592 KB Output is partially correct
4 Partially correct 325 ms 592 KB Output is partially correct
5 Partially correct 731 ms 1360 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Partially correct 114 ms 476 KB Output is partially correct
9 Partially correct 249 ms 768 KB Output is partially correct
10 Partially correct 711 ms 1296 KB Output is partially correct
11 Partially correct 712 ms 1240 KB Output is partially correct
12 Partially correct 672 ms 1272 KB Output is partially correct
13 Partially correct 667 ms 1168 KB Output is partially correct
14 Correct 4 ms 344 KB Output is correct
15 Incorrect 1 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -