oj.uz

답안 #1073363

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1073363 2024-08-24T13:31:02 Z Unforgettablepl 가장 긴 여행 (IOI23_longesttrip) C++17
15 / 100
 925 ms 1544 KB 
#pragma GCC optimize("Ofast","unroll-all-loops")
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> longest_trip(int N,int D){
    vector<vector<int>> adj(N);
    vector areConnected(N,vector<bool>(N));
    for(int i=0;i<N;i++) {
        for(int j=i+1;j<N;j++) {
            if(are_connected({i},{j})) {
                adj[i].emplace_back(j);
                adj[j].emplace_back(i);
                areConnected[i][j]=areConnected[j][i]=true;
            }
        }
    }
    {
        // Case 1 if two components
        int isTwo = -1;
        {
            vector<bool> visited(N);
            int curr = 0;
            function<void(int)> dfs = [&](int x) {
                if(visited[x])return;
                visited[x]=true;
                curr++;
                for(int&i:adj[x])dfs(i);
            };
            dfs(0);
            if(curr!=N) {
                if(curr>=N-curr)isTwo=curr;
                else {
                    for(int i=0;i<N;i++) {
                        if(!visited[i]){
                            isTwo=i;break;
                        }
                    }
                }
            }
        }
        if(isTwo!=-1) {
            vector<bool> visited(N);
            vector<int> ans;
            function<void(int)> dfs = [&](int x) {
                visited[x]=true;
                ans.emplace_back(x);
                for(int&i:adj[x])if(!visited[i]) {
                    dfs(i);
                    return;
                }
            };
            dfs(isTwo);
            return ans;
        }
    }
    vector<vector<int>> path(3);
    vector<bool> visited(N);
    function<int(int,int)> dfs = [&](int x,int def) {
        visited[x]=true;
        int state = def;
        int children = 0;
        for(int&i:adj[x])if(!visited[i]) {
            children++;
            if(children==2) {
                assert(dfs(i,2)==2);
                state=0;
                break;
            }
            auto ans = dfs(i,def);
            if(ans==0) {
                state = 0;
                break;
            }
        }
        path[state].emplace_back(x);
        return state;
    };
    auto curr = dfs(0,1);
    if(curr==1) {
        return path[1];
    }
    assert(curr==0);
    if(path[0].size()==1) {
        vector<int> ans = path[1];
        ans.emplace_back(path[0][0]);
        reverse(path[2].begin(),path[2].end());
        for(int&i:path[2])ans.emplace_back(i);
        return ans;
    }
    if(!areConnected[path[0][1]][path[1][0]])swap(path[1],path[2]);
    path[1].emplace_back(path[0][0]);
    path[0].erase(path[0].begin());
    reverse(path[0].begin(),path[0].end());
    reverse(path[2].begin(),path[2].end());
    auto ans = path[0];
    for(int&i:path[1])ans.emplace_back(i);
    for(int&i:path[2])ans.emplace_back(i);
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Correct 147 ms 440 KB Output is correct
4 Correct 406 ms 760 KB Output is correct
5 Correct 893 ms 972 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 127 ms 440 KB Output is correct
4 Correct 411 ms 716 KB Output is correct
5 Correct 925 ms 1056 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 23 ms 432 KB Output is correct
8 Correct 170 ms 444 KB Output is correct
9 Correct 356 ms 1104 KB Output is correct
10 Correct 820 ms 1316 KB Output is correct
11 Correct 874 ms 912 KB Output is correct
12 Correct 799 ms 984 KB Output is correct
13 Correct 881 ms 1316 KB Output is correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 22 ms 600 KB Output is correct
3 Correct 150 ms 452 KB Output is correct
4 Correct 416 ms 476 KB Output is correct
5 Correct 877 ms 1256 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 30 ms 600 KB Output is correct
8 Correct 147 ms 344 KB Output is correct
9 Correct 347 ms 752 KB Output is correct
10 Correct 858 ms 984 KB Output is correct
11 Correct 854 ms 1044 KB Output is correct
12 Correct 886 ms 1008 KB Output is correct
13 Correct 856 ms 820 KB Output is correct
14 Correct 9 ms 344 KB Output is correct
15 Incorrect 14 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Partially correct 172 ms 440 KB Output is partially correct
4 Partially correct 407 ms 980 KB Output is partially correct
5 Partially correct 858 ms 980 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 432 KB Output is correct
8 Partially correct 136 ms 452 KB Output is partially correct
9 Partially correct 313 ms 608 KB Output is partially correct
10 Partially correct 830 ms 1544 KB Output is partially correct
11 Partially correct 888 ms 992 KB Output is partially correct
12 Partially correct 807 ms 1076 KB Output is partially correct
13 Partially correct 838 ms 1068 KB Output is partially correct
14 Incorrect 1 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -