oj.uz

Submission #1052323

# Submission time Handle Problem Language Result Execution time Memory
1052323 2024-08-10T13:21:29 Z Zicrus Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 1756 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]);
    }

    volatile int idk = 0;
    for (int i = 1; i < res.size(); i++) {
        while (!mat[res[i-1]][res[i]] && (res[i] == k[0][bridge]))
            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:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     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 169 ms 1296 KB Output is correct

Subtask #1
5.0 / 5.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 Correct 115 ms 344 KB Output is correct
4 Correct 363 ms 988 KB Output is correct
5 Correct 683 ms 1260 KB Output is correct

Subtask #2
10.0 / 10.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 116 ms 344 KB Output is correct
4 Correct 353 ms 600 KB Output is correct
5 Correct 659 ms 1440 KB Output is correct
6 Correct 10 ms 348 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 121 ms 344 KB Output is correct
9 Correct 252 ms 560 KB Output is correct
10 Correct 710 ms 1584 KB Output is correct
11 Correct 675 ms 1208 KB Output is correct
12 Correct 675 ms 1096 KB Output is correct
13 Correct 693 ms 1176 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 18 ms 344 KB Output is correct
3 Correct 134 ms 600 KB Output is correct
4 Correct 348 ms 580 KB Output is correct
5 Correct 701 ms 1256 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Correct 114 ms 480 KB Output is correct
9 Correct 283 ms 592 KB Output is correct
10 Correct 683 ms 1276 KB Output is correct
11 Correct 717 ms 1420 KB Output is correct
12 Correct 741 ms 1756 KB Output is correct
13 Correct 721 ms 1192 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Execution timed out 3093 ms 344 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 13 ms 344 KB Output is correct
3 Partially correct 126 ms 344 KB Output is partially correct
4 Partially correct 358 ms 816 KB Output is partially correct
5 Partially correct 659 ms 1460 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Partially correct 111 ms 344 KB Output is partially correct
9 Partially correct 260 ms 344 KB Output is partially correct
10 Partially correct 701 ms 1076 KB Output is partially correct
11 Partially correct 695 ms 1168 KB Output is partially correct
12 Partially correct 749 ms 1264 KB Output is partially correct
13 Partially correct 706 ms 1120 KB Output is partially correct
14 Correct 4 ms 344 KB Output is correct
15 Execution timed out 3095 ms 344 KB Time limit exceeded
16 Halted 0 ms 0 KB -