oj.uz

Submission #1052313

# Submission time Handle Problem Language Result Execution time Memory
1052313 2024-08-10T13:17:50 Z Zicrus Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 1664 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-1] == k[0][bridge] || res[i] == k[0][bridge] ||
                                          res[i-1] == k[1][used] || res[i] == k[1][used]))
            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 0 ms 344 KB Output is correct
2 Correct 167 ms 1592 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 21 ms 344 KB Output is correct
3 Correct 142 ms 480 KB Output is correct
4 Correct 354 ms 704 KB Output is correct
5 Correct 676 ms 1652 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 23 ms 344 KB Output is correct
3 Correct 128 ms 600 KB Output is correct
4 Correct 336 ms 832 KB Output is correct
5 Correct 677 ms 1476 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 155 ms 344 KB Output is correct
9 Correct 243 ms 560 KB Output is correct
10 Correct 717 ms 1168 KB Output is correct
11 Correct 674 ms 1372 KB Output is correct
12 Correct 736 ms 1212 KB Output is correct
13 Correct 674 ms 1204 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Correct 139 ms 344 KB Output is correct
4 Correct 331 ms 712 KB Output is correct
5 Correct 688 ms 1144 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 82 ms 600 KB Output is correct
9 Correct 273 ms 560 KB Output is correct
10 Correct 769 ms 1308 KB Output is correct
11 Correct 728 ms 1296 KB Output is correct
12 Correct 684 ms 1192 KB Output is correct
13 Correct 607 ms 1488 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 8 ms 344 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Partially correct 111 ms 600 KB Output is partially correct
4 Partially correct 357 ms 796 KB Output is partially correct
5 Partially correct 673 ms 1664 KB Output is partially correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Partially correct 146 ms 344 KB Output is partially correct
9 Partially correct 254 ms 600 KB Output is partially correct
10 Partially correct 670 ms 1208 KB Output is partially correct
11 Partially correct 660 ms 1328 KB Output is partially correct
12 Partially correct 690 ms 1520 KB Output is partially correct
13 Partially correct 690 ms 1148 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Execution timed out 3035 ms 344 KB Time limit exceeded
16 Halted 0 ms 0 KB -