oj.uz

답안 #1000507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1000507 2024-06-17T16:03:19 Z Mardonbekhazratov 가장 긴 여행 (IOI23_longesttrip) C++17
40 / 100
 984 ms 1444 KB 
#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;

using namespace std;

vector<int>sub1(int n){
    vector<int>ans;
    for(int i=0;i<n;i++) ans.push_back(i);
    return ans;
}

int n;
vector<vector<int>>v;
vector<int>dp,a,vis;

void dfs(int x){
    int s=x;
    vis[x]=1;
    for(int z:v[x]){
        if(vis[z]!=1){
            if(vis[z]==0) dfs(z);
            if(dp[z]+1>dp[x]) s=z,dp[x]=dp[z]+1;
        }
    }
    vis[x]=2;
    a[x]=s;
}

vector<int>f(int x){
    dp.assign(n,0);
    a.resize(n);
    vis.assign(n,0);
    dfs(x);
    vector<int>ans;
    if(dp[x]==0) return ans;
    while(x!=a[x]){
        ans.push_back(x);
        x=a[x];
    }
    ans.push_back(x);
    return ans;
}

vector<int> longest_trip(int N, int D){
    if(D==3) return sub1(N);
    n=N;
    v.assign(N,vector<int>(0));
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(are_connected({i},{j})){
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    vector<int>ans;
    for(int i=0;i<N;i++){
        vector<int>b=f(i);
        if(b.size()>ans.size()) swap(b,ans);
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 177 ms 944 KB Output is correct

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Correct 161 ms 344 KB Output is correct
4 Correct 451 ms 484 KB Output is correct
5 Correct 938 ms 712 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 150 ms 600 KB Output is correct
9 Correct 304 ms 720 KB Output is correct
10 Correct 984 ms 700 KB Output is correct
11 Correct 919 ms 852 KB Output is correct
12 Correct 936 ms 708 KB Output is correct
13 Correct 901 ms 848 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 139 ms 448 KB Output is correct
4 Correct 446 ms 684 KB Output is correct
5 Correct 931 ms 1104 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 142 ms 344 KB Output is correct
9 Correct 311 ms 344 KB Output is correct
10 Correct 950 ms 620 KB Output is correct
11 Correct 859 ms 1108 KB Output is correct
12 Correct 944 ms 788 KB Output is correct
13 Correct 909 ms 696 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 59 ms 344 KB Output is correct
17 Correct 106 ms 344 KB Output is correct
18 Correct 162 ms 448 KB Output is correct
19 Correct 306 ms 444 KB Output is correct
20 Correct 340 ms 592 KB Output is correct
21 Correct 799 ms 852 KB Output is correct
22 Correct 914 ms 1320 KB Output is correct
23 Correct 849 ms 804 KB Output is correct
24 Correct 823 ms 788 KB Output is correct
25 Correct 9 ms 348 KB Output is correct
26 Correct 14 ms 344 KB Output is correct
27 Correct 45 ms 344 KB Output is correct
28 Correct 19 ms 344 KB Output is correct
29 Correct 23 ms 344 KB Output is correct
30 Correct 212 ms 340 KB Output is correct
31 Correct 190 ms 700 KB Output is correct
32 Correct 174 ms 600 KB Output is correct
33 Correct 295 ms 592 KB Output is correct
34 Correct 332 ms 460 KB Output is correct
35 Correct 284 ms 476 KB Output is correct
36 Correct 877 ms 864 KB Output is correct
37 Correct 885 ms 1280 KB Output is correct
38 Correct 857 ms 1084 KB Output is correct
39 Correct 912 ms 900 KB Output is correct
40 Correct 833 ms 856 KB Output is correct
41 Correct 816 ms 976 KB Output is correct
42 Correct 880 ms 964 KB Output is correct
43 Correct 890 ms 1444 KB Output is correct
44 Correct 850 ms 1088 KB Output is correct
45 Correct 6 ms 344 KB Output is correct
46 Correct 7 ms 344 KB Output is correct
47 Correct 30 ms 344 KB Output is correct
48 Correct 30 ms 344 KB Output is correct
49 Correct 32 ms 344 KB Output is correct
50 Correct 202 ms 612 KB Output is correct
51 Correct 204 ms 344 KB Output is correct
52 Correct 197 ms 432 KB Output is correct
53 Correct 321 ms 600 KB Output is correct
54 Correct 367 ms 344 KB Output is correct
55 Correct 358 ms 708 KB Output is correct
56 Correct 908 ms 868 KB Output is correct
57 Correct 912 ms 1052 KB Output is correct
58 Correct 961 ms 956 KB Output is correct
59 Correct 833 ms 1044 KB Output is correct
60 Correct 870 ms 1200 KB Output is correct
61 Correct 893 ms 576 KB Output is correct
62 Correct 873 ms 976 KB Output is correct
63 Correct 897 ms 1216 KB Output is correct
64 Correct 938 ms 856 KB Output is correct

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Partially correct 163 ms 956 KB Output is partially correct
4 Partially correct 424 ms 732 KB Output is partially correct
5 Partially correct 961 ms 848 KB Output is partially correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 34 ms 344 KB Output is correct
8 Partially correct 131 ms 344 KB Output is partially correct
9 Partially correct 323 ms 344 KB Output is partially correct
10 Partially correct 906 ms 1092 KB Output is partially correct
11 Partially correct 955 ms 1116 KB Output is partially correct
12 Partially correct 930 ms 1004 KB Output is partially correct
13 Partially correct 876 ms 524 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Incorrect 6 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -