oj.uz

Submission #916137

# Submission time Handle Problem Language Result Execution time Memory
916137 2024-01-25T11:14:10 Z chirathnirodha Longest Trip (IOI23_longesttrip) C++17
15 / 100
 694 ms 1976 KB 
#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define P push
#define I insert 
#define F first
#define S second
typedef long long ll;

vector<int> longest_trip(int n, int D){
    if(D==3){
        vector<int> tt;for(int i=0;i<n;i++)tt.PB(i);
        return tt;
    }
    vector<int> v[n];
    bool grid[n][n];
    for(int i=0;i<n;i++)v[i].clear();
    memset(grid,0,sizeof(grid));
 
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(are_connected({i},{j})){v[i].PB(j);v[j].PB(i); grid[i][j]=grid[j][i]=1;}
        }
    }
    vector<int> v1,v2;
    v1.PB(0);v2.PB(1);
    for(int i=2;i<n;i++){
        if(grid[i][v1.back()])v1.PB(i);
        else if(grid[i][v2.back()])v2.PB(i);
        else{
            for(int j=v2.size()-1;j>=0;j--)v1.PB(v2[j]);
            v2.clear();
            v2.PB(i);
        }
    }
    
    if(grid[v1.back()][v2[0]]){
        for(int i=0;i<v2.size();i++)v1.PB(v2[i]);
        return v1;
    }
    if(grid[v1.back()][v2.back()]){
        for(int i=v2.size()-1;i>=0;i--)v1.PB(v2[i]);
        return v1;
    }
    if(grid[v1[0]][v2[0]]){
        reverse(v1.begin(),v1.end());
        for(int i=0;i<v2.size();i++)v1.PB(v2[i]);
        return v1;
    }
    if(grid[v1[0]][v2.back()]){
        reverse(v1.begin(),v1.end());
        for(int i=v2.size()-1;i>=0;i--)v1.PB(v2[i]);
        return v1;
    }

    vector<int> ans;
    for(int i=0;i<v1.size();i++){
        for(int j=0;j<v2.size();j++){
            if(!grid[v1[i]][v2[j]])continue;
            for(int k=0;k<v1.size();k++){
                int x=(i-1-k+v1.size())%v1.size();
                ans.PB(v1[x]);
            }
            for(int k=0;k<v2.size();k++){
                int x=(j-1-k+v2.size())%v2.size();
                ans.PB(v2[x]);
            }
            return ans;
        }
    }
    if(v1.size()>v2.size()) return v1;
    else return v2;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i=0;i<v2.size();i++)v1.PB(v2[i]);
      |                     ~^~~~~~~~~~
longesttrip.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int i=0;i<v2.size();i++)v1.PB(v2[i]);
      |                     ~^~~~~~~~~~
longesttrip.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<v1.size();i++){
      |                 ~^~~~~~~~~~
longesttrip.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int j=0;j<v2.size();j++){
      |                     ~^~~~~~~~~~
longesttrip.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int k=0;k<v1.size();k++){
      |                         ~^~~~~~~~~~
longesttrip.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int k=0;k<v2.size();k++){
      |                         ~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 161 ms 1976 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 21 ms 492 KB Output is correct
3 Correct 120 ms 608 KB Output is correct
4 Correct 315 ms 1376 KB Output is correct
5 Correct 635 ms 1076 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 117 ms 692 KB Output is correct
9 Correct 237 ms 972 KB Output is correct
10 Correct 662 ms 1348 KB Output is correct
11 Correct 649 ms 1188 KB Output is correct
12 Correct 680 ms 1436 KB Output is correct
13 Correct 629 ms 1404 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 114 ms 856 KB Output is correct
4 Correct 329 ms 856 KB Output is correct
5 Correct 645 ms 1548 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Correct 110 ms 856 KB Output is correct
9 Correct 255 ms 888 KB Output is correct
10 Correct 629 ms 1620 KB Output is correct
11 Correct 694 ms 1620 KB Output is correct
12 Correct 646 ms 1652 KB Output is correct
13 Correct 673 ms 1368 KB Output is correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Incorrect 5 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 22 ms 344 KB Output is correct
3 Partially correct 114 ms 856 KB Output is partially correct
4 Partially correct 332 ms 972 KB Output is partially correct
5 Partially correct 637 ms 1836 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Partially correct 107 ms 696 KB Output is partially correct
9 Partially correct 247 ms 1112 KB Output is partially correct
10 Partially correct 640 ms 1616 KB Output is partially correct
11 Partially correct 660 ms 1624 KB Output is partially correct
12 Partially correct 651 ms 1608 KB Output is partially correct
13 Partially correct 645 ms 1920 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Incorrect 4 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -