oj.uz

Submission #1052268

# Submission time Handle Problem Language Result Execution time Memory
1052268 2024-08-10T12:52:31 Z Zicrus Longest Trip (IOI23_longesttrip) C++17
5 / 100
 755 ms 1668 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);
    vector<vector<bool>> mat(n, vector<bool>(n));
    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);
                mat[i][j] = true;
                mat[j][i] = true;
            }
            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, comp);
        comp = !comp;
    }
    if (k[0].size() < k[1].size()) swap(k[0], k[1]);

    ll mxDeg = 0, bridge = 0;
    for (int i = 0; i < k[0].size(); i++) {
        if (adj[k[0][i]].size() > mxDeg) {
            mxDeg = adj[k[0][i]].size();
            bridge = i;
        }
    }

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

    for (int i = 1; i < res.size(); i++) {
        if (!mat[res[i-1]][res[i]]) throw;
    }

    return res;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < k[0].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
longesttrip.cpp:51:33: 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]
   51 |         if (adj[k[0][i]].size() > mxDeg) {
      |             ~~~~~~~~~~~~~~~~~~~~^~~~~~~
longesttrip.cpp:59:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = bridge+1; i < k[0].size(); i++) {
      |                            ~~^~~~~~~~~~~~~
longesttrip.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < k[1].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
longesttrip.cpp:80:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = used+1; i < k[1].size(); i++) {
      |                          ~~^~~~~~~~~~~~~
longesttrip.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 1; i < res.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 157 ms 1084 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 15 ms 344 KB Output is correct
3 Correct 111 ms 480 KB Output is correct
4 Correct 372 ms 584 KB Output is correct
5 Correct 755 ms 928 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 31 ms 344 KB Output is correct
3 Correct 128 ms 344 KB Output is correct
4 Correct 348 ms 580 KB Output is correct
5 Correct 738 ms 1228 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Correct 121 ms 344 KB Output is correct
4 Correct 336 ms 344 KB Output is correct
5 Correct 669 ms 1384 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 16 ms 344 KB Output is correct
8 Correct 118 ms 592 KB Output is correct
9 Correct 277 ms 592 KB Output is correct
10 Correct 704 ms 1344 KB Output is correct
11 Correct 690 ms 1172 KB Output is correct
12 Correct 743 ms 1668 KB Output is correct
13 Correct 655 ms 1332 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Runtime error 0 ms 344 KB Execution killed with signal 6
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 20 ms 344 KB Output is correct
3 Partially correct 132 ms 600 KB Output is partially correct
4 Partially correct 350 ms 652 KB Output is partially correct
5 Partially correct 670 ms 1180 KB Output is partially correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -