제출 #1293579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293579		tschav_	세계 지도 (IOI25_worldmap)	C++20	0 / 100	45 ms	6252 KiB

worldmap

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


vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) {

    vector<vector<int>> adj;
    adj.resize(n+1,vector<int>{});

    for(int i = 0; i < m; ++i) {
        adj[A[i]].emplace_back(B[i]);
        adj[B[i]].emplace_back(A[i]);
    }

    if(m == 0){
        return vector<vector<int>>{vector<int>{1}};
    }

    vector<int> row;
    vector<bool> vis(n+1,false);

    int C = 0 ;

    auto dfs = [&](int ind, auto &&dfs) -> void {
        vis[ind]=true;
        ++C;
        for(auto &u : adj[ind]) {
            if(vis[u] or C==n) continue;

            row.emplace_back(ind);
            dfs(u,dfs);
        }
        if(C!=n)row.push_back(ind);
    };

    dfs(1, dfs);

    map<int,int>freq;
    int sz = 0;
    for(int i = 0; i < row.size();++i){
        if(freq[row[i]]){
            ++sz;
        }else{sz+=3;}
    }

     vector<vector<int>> ans(3 * sz, vector<int>(3 * sz, 1));


    vector<bool> F(n+1,false); int last= 0;
    for(int i = 0; i < row.size(); ++i) {
        int u = row[i];
        queue<int> Q;

        for(auto &v : adj[u]){
            Q.push(v);
        }
        if(F[u]){
            for(int j = 0; j < 3*sz;++j)ans[j][last]=u;
            ++last;
        }else{
        int p1 = last;
        int p2 = last+1;
        int p3 = last+2;
        for(int j = 0; j < 3 * sz; ++j){

            if(j & 1 or Q.empty()){
                ans[j][p1]=ans[j][p2]=ans[j][p3]=u;
            }else{
                ans[j][p1]=ans[j][p3]=u;
                ans[j][p2]=Q.front();
                Q.pop();
            }

        }
        last+=3;
        }
        F[u]=true;

    }

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56