oj.uz

Submission #916133

# Submission time Handle Problem Language Result Execution time Memory
916133 2024-01-25T11:10:25 Z chirathnirodha Longest Trip (IOI23_longesttrip) C++17
15 / 100
 774 ms 2036 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 0 ms 344 KB Output is correct
2 Correct 151 ms 1956 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 1 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 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 25 ms 344 KB Output is correct
3 Correct 127 ms 856 KB Output is correct
4 Correct 355 ms 872 KB Output is correct
5 Correct 724 ms 1684 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 128 ms 856 KB Output is correct
9 Correct 267 ms 936 KB Output is correct
10 Correct 745 ms 1376 KB Output is correct
11 Correct 696 ms 2036 KB Output is correct
12 Correct 677 ms 1576 KB Output is correct
13 Correct 710 ms 1452 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 32 ms 344 KB Output is correct
3 Correct 123 ms 856 KB Output is correct
4 Correct 324 ms 1648 KB Output is correct
5 Correct 696 ms 1668 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 28 ms 344 KB Output is correct
8 Correct 107 ms 592 KB Output is correct
9 Correct 227 ms 1220 KB Output is correct
10 Correct 739 ms 1792 KB Output is correct
11 Correct 644 ms 1540 KB Output is correct
12 Correct 671 ms 1916 KB Output is correct
13 Correct 711 ms 1900 KB Output is 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 -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Partially correct 112 ms 708 KB Output is partially correct
4 Partially correct 335 ms 1248 KB Output is partially correct
5 Partially correct 700 ms 1452 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Partially correct 114 ms 856 KB Output is partially correct
9 Partially correct 235 ms 1220 KB Output is partially correct
10 Partially correct 736 ms 1644 KB Output is partially correct
11 Partially correct 703 ms 1636 KB Output is partially correct
12 Partially correct 774 ms 1640 KB Output is partially correct
13 Partially correct 712 ms 1612 KB Output is partially correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Incorrect 4 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -