제출 #1205363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205363		Pacybwoah	Longest Trip (IOI23_longesttrip)	C++20	60 / 100	338 ms	748 KiB

longesttrip

#include "longesttrip.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
    struct DSU{
        int n;
        vector<int> dsu, sz;
        DSU(int _n){
            n = _n;
            dsu.resize(n + 1);
            sz.resize(n + 1);
            for(int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
        }
        int query(int x){
            if(dsu[x] == x) return dsu[x];
            dsu[x] = query(dsu[x]);
            return dsu[x];
        }
        void unite(int a, int b){
            a = query(a);
            b = query(b);
            if(a == b) return;
            if(sz[a] < sz[b]) swap(a, b);
            dsu[b] = a;
            sz[a] += sz[b];
        }
    };
}
std::vector<int> longest_trip(int n, int D){
    DSU dsu(n);
    vector<vector<int>> graph(n, vector<int>(n));
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            graph[i][j] = int(are_connected(vector<int>(1, i), vector<int>(1, j)));
            graph[j][i] = graph[i][j];
            if(graph[i][j]) dsu.unite(i, j);
        }
    }
    if(dsu.sz[dsu.query(0)] < n){
        int maxi = dsu.sz[dsu.query(0)], best = dsu.query(0);
        //cout << maxi << ' ' << best << endl;
        for(int i = 0; i < n; i++){
            if(i != dsu.query(i)) continue;
            if(maxi < dsu.sz[i]){
                best = i;
                maxi = dsu.sz[i];
            }
        }
        vector<int> ans;
        for(int i = 0; i < n; i++){
            if(dsu.query(i) == best) ans.push_back(i);
        }
        return ans;
    }
    vector<int> ans;
    vector<int> ord;
    for(int i = 0; i < n; i++) ord.push_back(i);
    for(int i = 1; i < n; i++){
        if(graph[0][i]){
            swap(ord[1], ord[i]);
            break;
        }
    }
    ans.push_back(ord[0]);
    ans.push_back(ord[1]);
    bool flag = 1;
    for(int i = 2; i < n; i++){
        if(flag){
            bool f2 = 0;
            for(int j = i; j < n; j++){
                for(int k = 0; k < i; k++){
                    if(graph[ans[k]][ord[j]]){
                        //cout << ans[k] << " " << ord[j] << endl;
                        f2 = 1;
                        vector<int> nans;
                        for(int l = k + 1; l < i; l++) nans.push_back(ans[l]);
                        for(int l = 0; l <= k; l++) nans.push_back(ans[l]);
                        nans.push_back(ord[j]);
                        swap(ord[j], ord[i]);
                        ans = nans;
                        break;
                    }
                }
                if(f2){
                    break;
                }
            }
        }
        else{
            vector<int> nans;
            if(graph[ans[0]][ord[i]]){
                nans.push_back(ord[i]);
                for(auto &x: ans) nans.push_back(x);
                ans = nans;
            }
            else{
                ans.push_back(ord[i]);
            }
        }
        if(graph[ans[0]][ans[i]]) flag = 1;
        else flag = 0;
    }
    return ans;
}

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