oj.uz

Submission #1014190

# Submission time Handle Problem Language Result Execution time Memory
1014190 2024-07-04T13:52:04 Z JakobZorz Longest Trip (IOI23_longesttrip) C++17
15 / 100
 908 ms 1292 KB 
#include"longesttrip.h"
#include<iostream>
using namespace std;

int n;
vector<int>nodes[500];

vector<int>longest_trip(int N,int D){
    n=N;
    for(int i=0;i<n;i++)
        nodes[i].clear();
    
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(are_connected({i},{j})){
                nodes[i].push_back(j);
                nodes[j].push_back(i);
                //cout<<"CONN "<<i<<" "<<j<<"\n";
            }
        }
    }
    vector<int>res={0};
    vector<bool>vis(n);
    vis[0]=true;
    while(true){
        int node=res.back();
        //cout<<"VIS "<<node<<"\n";
        for(int ne:nodes[node])
            if(!vis[ne]){
                res.push_back(ne);
                break;
            }
        vis[res.back()]=true;
        if(node==res.back())
            break;
    }
    // all unvisited are now a strongly connected component
    for(int i=0;i<(int)res.size();i++){
        for(int ne:nodes[res[i]]){
            if(!vis[ne]){
                vector<int>res2;
                for(int j=0;j<n;j++)
                    if(!vis[j])
                        res2.push_back(j);
                for(int j=i;j<(int)res.size();j++)
                    res2.push_back(res[j]);
                for(int j=0;j<i;j++)
                    res2.push_back(res[j]);
                return res2;
            }
        }
    }
    if(2*res.size()<n){
        vector<int>res2;
        for(int j=0;j<n;j++)
            if(!vis[j])
                res2.push_back(j);
        return res2;
    }
    return res;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:53:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     if(2*res.size()<n){
      |        ~~~~~~~~~~~~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Correct 111 ms 344 KB Output is correct
4 Correct 446 ms 344 KB Output is correct
5 Correct 870 ms 1124 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 30 ms 344 KB Output is correct
3 Correct 145 ms 344 KB Output is correct
4 Correct 416 ms 480 KB Output is correct
5 Correct 854 ms 892 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 160 ms 344 KB Output is correct
9 Correct 333 ms 720 KB Output is correct
10 Correct 794 ms 788 KB Output is correct
11 Correct 825 ms 652 KB Output is correct
12 Correct 825 ms 636 KB Output is correct
13 Correct 820 ms 900 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 31 ms 344 KB Output is correct
3 Correct 148 ms 600 KB Output is correct
4 Correct 369 ms 600 KB Output is correct
5 Correct 848 ms 1044 KB Output is correct
6 Correct 11 ms 596 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Correct 165 ms 600 KB Output is correct
9 Correct 324 ms 600 KB Output is correct
10 Correct 805 ms 1268 KB Output is correct
11 Correct 773 ms 896 KB Output is correct
12 Correct 808 ms 792 KB Output is correct
13 Correct 825 ms 628 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Incorrect 2 ms 344 KB Incorrect
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 23 ms 344 KB Output is correct
3 Partially correct 150 ms 600 KB Output is partially correct
4 Partially correct 389 ms 700 KB Output is partially correct
5 Partially correct 791 ms 1048 KB Output is partially correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 35 ms 344 KB Output is correct
8 Partially correct 142 ms 452 KB Output is partially correct
9 Partially correct 329 ms 592 KB Output is partially correct
10 Partially correct 835 ms 864 KB Output is partially correct
11 Partially correct 842 ms 592 KB Output is partially correct
12 Partially correct 854 ms 1292 KB Output is partially correct
13 Partially correct 908 ms 988 KB Output is partially correct
14 Correct 10 ms 344 KB Output is correct
15 Correct 8 ms 340 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -