oj.uz

Submission #1052290

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

    volatile int idk = 0;
    vst = vector<bool>(n);
    for (int i = 0; i < res.size(); i++) {
        while (vst[i])
            idk++;
        vst[i] = true;
        if (i == 0) continue;
        while (!mat[res[i-1]][res[i]])
            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: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:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; 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 159 ms 1396 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 18 ms 344 KB Output is correct
3 Correct 134 ms 344 KB Output is correct
4 Correct 342 ms 736 KB Output is correct
5 Correct 739 ms 1196 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 18 ms 344 KB Output is correct
3 Correct 123 ms 480 KB Output is correct
4 Correct 331 ms 620 KB Output is correct
5 Correct 690 ms 1232 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 99 ms 684 KB Output is correct
9 Correct 268 ms 596 KB Output is correct
10 Correct 705 ms 1172 KB Output is correct
11 Correct 684 ms 1168 KB Output is correct
12 Correct 710 ms 1244 KB Output is correct
13 Correct 684 ms 1244 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 130 ms 344 KB Output is correct
4 Correct 354 ms 748 KB Output is correct
5 Correct 706 ms 1404 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Correct 107 ms 344 KB Output is correct
9 Correct 260 ms 704 KB Output is correct
10 Correct 740 ms 1276 KB Output is correct
11 Correct 684 ms 1096 KB Output is correct
12 Correct 715 ms 1320 KB Output is correct
13 Correct 684 ms 1488 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Execution timed out 3073 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 6 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Partially correct 104 ms 464 KB Output is partially correct
4 Partially correct 270 ms 584 KB Output is partially correct
5 Partially correct 628 ms 1016 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Partially correct 115 ms 456 KB Output is partially correct
9 Partially correct 204 ms 564 KB Output is partially correct
10 Partially correct 630 ms 1196 KB Output is partially correct
11 Partially correct 728 ms 1492 KB Output is partially correct
12 Partially correct 686 ms 1508 KB Output is partially correct
13 Partially correct 698 ms 1172 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Execution timed out 3092 ms 344 KB Time limit exceeded
16 Halted 0 ms 0 KB -