oj.uz

Submission #1065128

# Submission time Handle Problem Language Result Execution time Memory
1065128 2024-08-18T23:53:30 Z vjudge1 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 865 ms 1380 KB 
#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[256];
bitset<256>vis;
void dfs(int n){
    if(vis[n])return;
    vis[n]=1;
    for(auto i:adj[n])
        dfs(i);
}
vector<int>path;
void dfs2(int n){
    path.push_back(n);
    vis[n]=1;
    for(auto i:adj[n])
        if(!vis[i])
            return dfs2(i);
}
vector<int> longest_trip(int N, int D){
    for(int i=0;i<N;i++)
        adj[i].clear();
    for(int i=1;i<N;i++) for(int j=i;j--;)
        if(are_connected({i},{j}))
            adj[i].push_back(j),
            adj[j].push_back(i);
    vis.reset();
    dfs(0);
    if(vis.count()!=N){
        vector<int>a,b;
        for(int i=0;i<N;i++)
            if(!vis[i])
                a.push_back(i);
            else b.push_back(i);
        return a.size()>b.size()?a:b;
    }
    vis.reset();
    path.clear();
    dfs2(0);
    if(path.size()==N)
        return path;
    for(auto x:adj[0])
        if(!vis[x]) {
            vector<int>v2;
            vis[x]=1;
            for(int i=0;i<N;i++)
                if(!vis[i])v2.push_back(i);
            v2.push_back(x);
            for(auto i:path)
                v2.push_back(i);
            return v2;
        }
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:29:19: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     if(vis.count()!=N){
      |        ~~~~~~~~~~~^~~
longesttrip.cpp:40:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if(path.size()==N)
      |        ~~~~~~~~~~~^~~
longesttrip.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 210 ms 1252 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 15 ms 344 KB Output is correct
3 Correct 163 ms 344 KB Output is correct
4 Correct 381 ms 720 KB Output is correct
5 Correct 822 ms 924 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 20 ms 344 KB Output is correct
3 Correct 138 ms 444 KB Output is correct
4 Correct 413 ms 708 KB Output is correct
5 Correct 863 ms 696 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 164 ms 344 KB Output is correct
9 Correct 294 ms 344 KB Output is correct
10 Correct 838 ms 896 KB Output is correct
11 Correct 804 ms 1380 KB Output is correct
12 Correct 864 ms 904 KB Output is correct
13 Correct 855 ms 920 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 24 ms 344 KB Output is correct
3 Correct 137 ms 344 KB Output is correct
4 Correct 432 ms 488 KB Output is correct
5 Correct 838 ms 1184 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 29 ms 344 KB Output is correct
8 Correct 139 ms 344 KB Output is correct
9 Correct 324 ms 732 KB Output is correct
10 Correct 805 ms 1280 KB Output is correct
11 Correct 865 ms 928 KB Output is correct
12 Correct 815 ms 900 KB Output is correct
13 Correct 849 ms 596 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Runtime error 2 ms 600 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Partially correct 153 ms 344 KB Output is partially correct
4 Partially correct 395 ms 344 KB Output is partially correct
5 Partially correct 836 ms 1172 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Partially correct 144 ms 444 KB Output is partially correct
9 Partially correct 307 ms 600 KB Output is partially correct
10 Partially correct 854 ms 1024 KB Output is partially correct
11 Partially correct 835 ms 940 KB Output is partially correct
12 Partially correct 814 ms 592 KB Output is partially correct
13 Partially correct 838 ms 1180 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Runtime error 2 ms 600 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -