제출 #840052

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
840052	2023-08-31 03:14:57	angelo_torres	가장 긴 여행 (IOI23_longesttrip)	C++17	5 / 100	1055 ms	328 KiB

longesttrip

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "longesttrip.h"
#define sz(v) (int) v.size()
#define ff first
#define ss second
using namespace std;
typedef pair<int,int> ii;
vector<int> longest_trip(int N, int D)
{
    vector<vector<bool>> A(N);
    for(int i = 0; i < N; ++i) A[i].resize(N);
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < i; ++j){
            A[i][j] = are_connected({i},{j});
            A[j][i] = A[i][j];
        }
    }
    vector<int> G(N);
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j) if(A[i][j]) G[i]++;
    }
    int x = 0;
    for(int i = 1; i < N; ++i){
        if(G[i] < G[x]) x = i;
    }
    vector<int> ans;
    if(G[x] <= (N/2)-1){
        for(int i = 0; i < N; ++i){
            if((i == x) || A[x][i]) continue;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60