oj.uz

Submission #1052327

# Submission time Handle Problem Language Result Execution time Memory
1052327 2024-08-10T13:25:21 Z Zicrus Longest Trip (IOI23_longesttrip) C++17
15 / 100
 751 ms 1580 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[k[0][bridge]]) {
        if (vst[e]) continue;
        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; i < k[1].size(); i++) {
        res.push_back(k[1][i]);
    }
    for (int i = 0; i < used; i++) {
        res.push_back(k[1][i]);
    }

    if (!mat[k[0].front()][k[0].back()]) throw;

    // res[i] == k[0][bridge]
    // bridge == 0
    volatile int idk = 0;
    for (int i = 1; i < res.size(); i++) {
        while (!mat[res[i-1]][res[i]] && (bridge == 0))
            idk++;
    }

    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:26: 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; i < k[1].size(); i++) {
      |                        ~~^~~~~~~~~~~~~
longesttrip.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 1; i < res.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 184 ms 1360 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 127 ms 712 KB Output is correct
4 Correct 350 ms 692 KB Output is correct
5 Correct 709 ms 1452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 29 ms 344 KB Output is correct
3 Correct 138 ms 344 KB Output is correct
4 Correct 362 ms 1104 KB Output is correct
5 Correct 713 ms 1400 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Correct 122 ms 344 KB Output is correct
9 Correct 248 ms 804 KB Output is correct
10 Correct 681 ms 1200 KB Output is correct
11 Correct 682 ms 1260 KB Output is correct
12 Correct 751 ms 1196 KB Output is correct
13 Correct 709 ms 1180 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 116 ms 344 KB Output is correct
4 Correct 362 ms 988 KB Output is correct
5 Correct 700 ms 1348 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Correct 101 ms 484 KB Output is correct
9 Correct 283 ms 844 KB Output is correct
10 Correct 656 ms 1472 KB Output is correct
11 Correct 700 ms 1232 KB Output is correct
12 Correct 703 ms 1244 KB Output is correct
13 Correct 703 ms 1508 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Runtime error 1 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 21 ms 344 KB Output is correct
3 Partially correct 124 ms 344 KB Output is partially correct
4 Partially correct 343 ms 688 KB Output is partially correct
5 Partially correct 658 ms 1580 KB Output is partially correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Partially correct 124 ms 600 KB Output is partially correct
9 Partially correct 286 ms 784 KB Output is partially correct
10 Partially correct 681 ms 1324 KB Output is partially correct
11 Partially correct 718 ms 1172 KB Output is partially correct
12 Partially correct 675 ms 1368 KB Output is partially correct
13 Partially correct 652 ms 1240 KB Output is partially correct
14 Correct 5 ms 344 KB Output is correct
15 Runtime error 1 ms 344 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -