제출 #844834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844834		vjudge1	가장 긴 여행 (IOI23_longesttrip)	C++17	60 / 100	746 ms	2228 KiB

longesttrip

#include "longesttrip.h"

// 123
#include <bits/stdc++.h>
using namespace std;

std::vector<int> longest_trip(int N, int D) {
        if (D == 3) {
                vector<int> ans(N);
                iota(ans.begin(), ans.end(), 0);
                return ans;
        } else {
                vector<vector<int>> d(N, vector<int>(N));
                vector<vector<int>> adj(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);
                                        d[i][j] = d[j][i] = 1;
                                }
                        }
                }
                if (D == 2) {
                        vector<int> ans(1, 0);
                        vector<int> vis(N, 0);
                        vis[0] = 1;
                        while (ans.size() + 2 <= N) {
                                int i = 0, j = 0;
                                for (; i < N; i++) {
                                        if (vis[i] == 0) break;
                                }
                                for (j = i + 1; j < N; j++) {
                                        if (vis[j] == 0) break;
                                }
                                assert(i < N && j < N);
                                int x = ans.back();
                                if (d[x][i] && d[i][j]) {
                                        ans.emplace_back(i), ans.emplace_back(j);
                                        vis[i] = vis[j] = 1;
                                } else if (d[x][j] && d[j][i]) {
                                        ans.emplace_back(j), ans.emplace_back(i);
                                        vis[i] = vis[j] = 1;
                                } else {
                                        assert(d[x][i] && d[x][j]);
                                        ans.emplace_back(i);
                                        vis[i] = 1;
                                }
                        }
                        int i = 0;
                        for (; i < N; i++) {
                                if (vis[i] == 0) break;
                        }
                        if (ans.size() == N - 1) {
                                if (d[ans.back()][i]) {
                                        ans.emplace_back(i);
                                } else if (d[ans.front()][i]) {
                                        ans.insert(ans.begin(), i);
                                } else {
                                        assert(0);
                                }
                        }
                        return ans;
                } else {
                        vector<int> vis(N, 0);
                        int cc = 0;
                        vector<int> ls[2];
                        function<void(int, vector<int>&)> dfs = [&](int u, vector<int>& ls) {
                                vis[u] = 1;
                                ls.emplace_back(u);
                                for (int v : adj[u]) {
                                        if (!vis[v]) dfs(v, ls);
                                }
                        };
                        for (int i = 0; i < N; i++) {
                                if (!vis[i]) dfs(i, ls[cc++]);
                        }
                        if (cc == 2) {
                                if (ls[0].size() < ls[1].size()) swap(ls[0], ls[1]);
                                return ls[0];
                        }
                        deque<int> ans;
                        auto add = [&](int x, int _) {
                                if (_) {
                                        ans.emplace_back(x);
                                } else {
                                        ans.emplace_front(x);
                                }
                        };
                        auto rotate = [&](int x) {
                                deque<int> tmp;
                                while (ans.back() != x) {
                                        tmp.emplace_back(ans.back());
                                        ans.pop_back();
                                }
                                ans.pop_back();
                                tmp.emplace_back(x);
                                while (ans.size()) {
                                        tmp.emplace_front(ans.front());
                                        ans.pop_front();
                                }
                                ans = tmp;
                        };
                        function<void(int, int)> solve = [&](int u, int _) {
                                vis[u] = 0;
                                add(u, _);
                                int fst = 1;
                                for (int v : adj[u]) {
                                        if (vis[v] == 0) continue;
                                        if (fst) {
                                                solve(v, _);
                                        } else {
                                                int x = ans.front();
                                                int y = ans.back();
                                                if (d[x][v]) {
                                                        solve(v, 0);
                                                } else if (d[y][v]) {
                                                        solve(v, 1);
                                                } else {
                                                        assert(d[x][y]);
                                                        rotate(u);
                                                        solve(v, 1);
                                                }
                                        }
                                        fst = 0;
                                }
                        };
                        solve(0, 0);
                        vector<int> res;
                        for (int i : ans) res.emplace_back(i);
                        return res;
                }
        }
}

컴파일 시 표준 에러 (stderr) 메시지

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:28:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |                         while (ans.size() + 2 <= N) {
      |                                ~~~~~~~~~~~~~~~^~~~
longesttrip.cpp:54:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |                         if (ans.size() == N - 1) {
      |                             ~~~~~~~~~~~^~~~~~~~

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