oj.uz

Submission #1052324

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

    // res[i] == k[0][bridge]
    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: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 = 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 167 ms 1364 KB Output is correct

Subtask #1
5.0 / 5.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 117 ms 484 KB Output is correct
4 Correct 300 ms 776 KB Output is correct
5 Correct 683 ms 2024 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 21 ms 344 KB Output is correct
3 Correct 114 ms 344 KB Output is correct
4 Correct 340 ms 580 KB Output is correct
5 Correct 703 ms 1600 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Correct 121 ms 468 KB Output is correct
9 Correct 251 ms 492 KB Output is correct
10 Correct 654 ms 1168 KB Output is correct
11 Correct 663 ms 1028 KB Output is correct
12 Correct 646 ms 1496 KB Output is correct
13 Correct 721 ms 1168 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 27 ms 344 KB Output is correct
3 Correct 125 ms 344 KB Output is correct
4 Correct 345 ms 848 KB Output is correct
5 Correct 690 ms 1240 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Correct 127 ms 488 KB Output is correct
9 Correct 256 ms 696 KB Output is correct
10 Correct 710 ms 1176 KB Output is correct
11 Correct 688 ms 1164 KB Output is correct
12 Correct 705 ms 1344 KB Output is correct
13 Correct 678 ms 1352 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Execution timed out 3089 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 19 ms 344 KB Output is correct
3 Partially correct 107 ms 344 KB Output is partially correct
4 Partially correct 338 ms 784 KB Output is partially correct
5 Partially correct 735 ms 1336 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Partially correct 130 ms 456 KB Output is partially correct
9 Partially correct 280 ms 808 KB Output is partially correct
10 Partially correct 642 ms 1164 KB Output is partially correct
11 Partially correct 739 ms 1424 KB Output is partially correct
12 Partially correct 673 ms 1264 KB Output is partially correct
13 Partially correct 636 ms 1420 KB Output is partially correct
14 Correct 5 ms 344 KB Output is correct
15 Execution timed out 3058 ms 344 KB Time limit exceeded
16 Halted 0 ms 0 KB -