oj.uz

Submission #1052311

# Submission time Handle Problem Language Result Execution time Memory
1052311 2024-08-10T13:15:27 Z Zicrus Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 1616 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]])
            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 146 ms 1136 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 116 ms 700 KB Output is correct
4 Correct 348 ms 744 KB Output is correct
5 Correct 709 ms 1172 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 16 ms 344 KB Output is correct
3 Correct 102 ms 700 KB Output is correct
4 Correct 367 ms 600 KB Output is correct
5 Correct 736 ms 1480 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 19 ms 600 KB Output is correct
8 Correct 129 ms 472 KB Output is correct
9 Correct 268 ms 812 KB Output is correct
10 Correct 712 ms 1064 KB Output is correct
11 Correct 728 ms 1576 KB Output is correct
12 Correct 687 ms 1240 KB Output is correct
13 Correct 701 ms 1304 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 13 ms 344 KB Output is correct
3 Correct 125 ms 600 KB Output is correct
4 Correct 267 ms 584 KB Output is correct
5 Correct 728 ms 1356 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 116 ms 856 KB Output is correct
9 Correct 256 ms 808 KB Output is correct
10 Correct 682 ms 1464 KB Output is correct
11 Correct 698 ms 1364 KB Output is correct
12 Correct 673 ms 1476 KB Output is correct
13 Correct 690 ms 1296 KB Output is correct
14 Correct 5 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 18 ms 344 KB Output is correct
3 Partially correct 125 ms 472 KB Output is partially correct
4 Partially correct 377 ms 800 KB Output is partially correct
5 Partially correct 709 ms 1300 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Partially correct 135 ms 344 KB Output is partially correct
9 Partially correct 290 ms 708 KB Output is partially correct
10 Partially correct 678 ms 1092 KB Output is partially correct
11 Partially correct 698 ms 1428 KB Output is partially correct
12 Partially correct 672 ms 1040 KB Output is partially correct
13 Partially correct 716 ms 1616 KB Output is partially correct
14 Correct 4 ms 344 KB Output is correct
15 Execution timed out 3043 ms 344 KB Time limit exceeded
16 Halted 0 ms 0 KB -