oj.uz

Submission #916151

# Submission time Handle Problem Language Result Execution time Memory
916151 2024-01-25T11:40:16 Z chirathnirodha Longest Trip (IOI23_longesttrip) C++17
60 / 100
 792 ms 1956 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-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 170 ms 1944 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 416 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 344 KB Output is correct
3 Correct 114 ms 600 KB Output is correct
4 Correct 364 ms 1112 KB Output is correct
5 Correct 645 ms 1372 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Correct 110 ms 604 KB Output is correct
9 Correct 239 ms 1224 KB Output is correct
10 Correct 688 ms 1328 KB Output is correct
11 Correct 657 ms 1292 KB Output is correct
12 Correct 671 ms 1852 KB Output is correct
13 Correct 645 ms 1472 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Correct 135 ms 860 KB Output is correct
4 Correct 345 ms 1232 KB Output is correct
5 Correct 706 ms 1636 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Correct 125 ms 856 KB Output is correct
9 Correct 253 ms 1128 KB Output is correct
10 Correct 675 ms 1600 KB Output is correct
11 Correct 728 ms 1708 KB Output is correct
12 Correct 693 ms 1892 KB Output is correct
13 Correct 763 ms 1612 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Correct 49 ms 344 KB Output is correct
17 Correct 77 ms 600 KB Output is correct
18 Correct 125 ms 856 KB Output is correct
19 Correct 248 ms 1220 KB Output is correct
20 Correct 252 ms 864 KB Output is correct
21 Correct 718 ms 1736 KB Output is correct
22 Correct 792 ms 1580 KB Output is correct
23 Correct 692 ms 1572 KB Output is correct
24 Correct 740 ms 1812 KB Output is correct
25 Correct 11 ms 344 KB Output is correct
26 Correct 9 ms 344 KB Output is correct
27 Correct 28 ms 344 KB Output is correct
28 Correct 20 ms 344 KB Output is correct
29 Correct 23 ms 596 KB Output is correct
30 Correct 159 ms 696 KB Output is correct
31 Correct 167 ms 952 KB Output is correct
32 Correct 170 ms 952 KB Output is correct
33 Correct 271 ms 856 KB Output is correct
34 Correct 243 ms 972 KB Output is correct
35 Correct 277 ms 1372 KB Output is correct
36 Correct 768 ms 1624 KB Output is correct
37 Correct 668 ms 1400 KB Output is correct
38 Correct 688 ms 1316 KB Output is correct
39 Correct 731 ms 1524 KB Output is correct
40 Correct 669 ms 1936 KB Output is correct
41 Correct 664 ms 1356 KB Output is correct
42 Correct 783 ms 1064 KB Output is correct
43 Correct 668 ms 1524 KB Output is correct
44 Correct 716 ms 1424 KB Output is correct
45 Correct 9 ms 596 KB Output is correct
46 Correct 9 ms 344 KB Output is correct
47 Correct 24 ms 344 KB Output is correct
48 Correct 23 ms 344 KB Output is correct
49 Correct 22 ms 344 KB Output is correct
50 Correct 152 ms 1452 KB Output is correct
51 Correct 144 ms 948 KB Output is correct
52 Correct 161 ms 696 KB Output is correct
53 Correct 241 ms 900 KB Output is correct
54 Correct 245 ms 972 KB Output is correct
55 Correct 277 ms 976 KB Output is correct
56 Correct 701 ms 1448 KB Output is correct
57 Correct 722 ms 1360 KB Output is correct
58 Correct 721 ms 1664 KB Output is correct
59 Correct 686 ms 1356 KB Output is correct
60 Correct 683 ms 1640 KB Output is correct
61 Correct 703 ms 1472 KB Output is correct
62 Correct 731 ms 1548 KB Output is correct
63 Correct 729 ms 1420 KB Output is correct
64 Correct 764 ms 1616 KB Output is correct

Subtask #4
19.999999998 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Partially correct 124 ms 856 KB Output is partially correct
4 Partially correct 361 ms 1012 KB Output is partially correct
5 Partially correct 693 ms 1120 KB Output is partially correct
6 Correct 7 ms 500 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Partially correct 109 ms 600 KB Output is partially correct
9 Partially correct 251 ms 972 KB Output is partially correct
10 Partially correct 756 ms 1916 KB Output is partially correct
11 Partially correct 767 ms 1348 KB Output is partially correct
12 Partially correct 688 ms 1624 KB Output is partially correct
13 Partially correct 673 ms 1588 KB Output is partially correct
14 Correct 11 ms 596 KB Output is correct
15 Correct 9 ms 340 KB Output is correct
16 Correct 35 ms 344 KB Output is correct
17 Partially correct 77 ms 600 KB Output is partially correct
18 Partially correct 114 ms 1188 KB Output is partially correct
19 Partially correct 229 ms 960 KB Output is partially correct
20 Partially correct 242 ms 888 KB Output is partially correct
21 Correct 9 ms 596 KB Output is correct
22 Correct 8 ms 344 KB Output is correct
23 Correct 20 ms 344 KB Output is correct
24 Correct 17 ms 344 KB Output is correct
25 Correct 23 ms 344 KB Output is correct
26 Partially correct 170 ms 952 KB Output is partially correct
27 Partially correct 165 ms 692 KB Output is partially correct
28 Partially correct 163 ms 948 KB Output is partially correct
29 Partially correct 255 ms 856 KB Output is partially correct
30 Partially correct 268 ms 968 KB Output is partially correct
31 Partially correct 250 ms 1124 KB Output is partially correct
32 Correct 7 ms 344 KB Output is correct
33 Correct 8 ms 344 KB Output is correct
34 Correct 21 ms 344 KB Output is correct
35 Correct 20 ms 344 KB Output is correct
36 Correct 19 ms 344 KB Output is correct
37 Partially correct 152 ms 704 KB Output is partially correct
38 Partially correct 165 ms 952 KB Output is partially correct
39 Partially correct 170 ms 700 KB Output is partially correct
40 Partially correct 240 ms 1368 KB Output is partially correct
41 Partially correct 261 ms 1112 KB Output is partially correct
42 Partially correct 262 ms 1124 KB Output is partially correct
43 Partially correct 698 ms 1588 KB Output is partially correct
44 Partially correct 783 ms 1548 KB Output is partially correct
45 Partially correct 745 ms 1668 KB Output is partially correct
46 Partially correct 717 ms 1956 KB Output is partially correct
47 Partially correct 718 ms 1524 KB Output is partially correct
48 Partially correct 719 ms 1668 KB Output is partially correct
49 Partially correct 755 ms 1356 KB Output is partially correct
50 Partially correct 689 ms 1340 KB Output is partially correct
51 Partially correct 747 ms 1604 KB Output is partially correct
52 Partially correct 745 ms 1576 KB Output is partially correct
53 Partially correct 700 ms 1644 KB Output is partially correct
54 Partially correct 680 ms 1392 KB Output is partially correct
55 Partially correct 708 ms 1496 KB Output is partially correct
56 Partially correct 740 ms 1652 KB Output is partially correct
57 Partially correct 695 ms 1416 KB Output is partially correct
58 Partially correct 700 ms 1788 KB Output is partially correct
59 Partially correct 703 ms 1528 KB Output is partially correct
60 Partially correct 710 ms 1396 KB Output is partially correct
61 Partially correct 776 ms 1520 KB Output is partially correct
62 Partially correct 670 ms 1336 KB Output is partially correct
63 Partially correct 684 ms 1664 KB Output is partially correct
64 Partially correct 708 ms 1460 KB Output is partially correct
65 Partially correct 687 ms 1920 KB Output is partially correct
66 Partially correct 675 ms 1656 KB Output is partially correct
67 Partially correct 701 ms 1072 KB Output is partially correct
68 Partially correct 706 ms 1568 KB Output is partially correct
69 Partially correct 737 ms 1648 KB Output is partially correct
70 Partially correct 676 ms 1432 KB Output is partially correct
71 Partially correct 670 ms 1324 KB Output is partially correct
72 Partially correct 659 ms 1680 KB Output is partially correct
73 Partially correct 691 ms 1656 KB Output is partially correct
74 Partially correct 716 ms 1916 KB Output is partially correct
75 Partially correct 738 ms 1332 KB Output is partially correct
76 Partially correct 691 ms 1120 KB Output is partially correct
77 Partially correct 685 ms 1424 KB Output is partially correct
78 Partially correct 664 ms 1920 KB Output is partially correct
79 Partially correct 653 ms 1632 KB Output is partially correct
80 Partially correct 704 ms 1668 KB Output is partially correct
81 Partially correct 663 ms 832 KB Output is partially correct
82 Partially correct 696 ms 1100 KB Output is partially correct