제출 #1293953

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

worldmap

#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 45;
vector<int> adj[N], ord1, ord2;
bool adj1[N][N];
int par[N];
bool vis[N];
void dfs(int v, int pr){
    vis[v] = true;
    par[v] = pr;
    ord1.pb(v);
    for(auto u:adj[v]){
        if(!vis[u]){
            dfs(u, v);
            ord1.pb(v);
        }
    }
}

vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b){
    for(int i = 0; i < m; i++){
        adj[a[i]].pb(b[i]);
        adj[b[i]].pb(a[i]);
        adj1[a[i]][b[i]] = 1;
        adj1[b[i]][a[i]] = 1;
    }
    dfs(1, 0);
    vector<vector<int>> ans;
    // for(int i = 1; i <= n; i++) cout << par[i] << " ";
    // cout << endl;
    // for(auto v:ord1) cout << v << " ";
    // cout << endl;
    ord1.pb(1);
    for(int i = 0; i < ord1.size(); i++){
        vector<int> f1, f2;
        int nd = ord1[i];
        while(nd != 0){
            f1.pb(nd);
            f1.pb(nd);
            nd = par[nd];
        }
        // for(int j = 0; j < f1.size(); j++) cout << f1[j] << " ";
        // cout << endl;
        for(int j = 0; j < 2 * n - f1.size(); j++) f2.pb(ord1[i]);
        for(int j = 0; j < f1.size(); j++) f2.pb(f1[j]);
        f2.pb(0), f2.pb(0);
        ans.pb(f2);
        // for(int j = 0; j < f2.size(); j++){
        //     cout << f2[j] <<  " ";        
        // }
        // cout << endl;
    }

    // for(int i = 0; i < 2 * n; i++){
    //     for(int j = 0; j < 2 * n; j++){
    //         cout << ans[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // for(int i = 0; i < 2 * n; i++) cout << ans[i].size() << " ";
    // cout << endl;
    for(int i = 0; i < 2 * n; i++){
        int v = ord1[i], idx = 0;
        while(ans[i][idx] == v or ans[i][idx] == par[v]){
            idx++;
            //if(i == 1) cout << "HERE" << endl;
        }
        //if(i == 1) cout << idx << " " << v << par[v] << endl;
        for(int j = idx; j < 2 * n; j+=4){
            if(!adj1[v][ans[i][j]]) continue;
            if(!adj1[v][par[ans[i][j]]]){
                ans[i][j + 1] = v;
                ans[i][j + 2] = ans[i][j];
            }else{
                ans[i][j + 1] = v;
            }
        }
    }
    // for(int i = 0; i < 2 * n; i++){
    //     for(int j = 0; j < 2 * n; j++){
    //         cout << ans[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    return ans;
}

// signed main(){
//     vector<int> a = {1, 2, 2, 4, 5, 1, 2, 2, 4};
//     vector<int> b = {2, 3, 4, 5, 6, 6, 5, 6, 6};
//     vector<int> a1 = {1, 1, 2, 2, 3, 4, 5};
//     vector<int> b1 = {3, 4, 3, 5, 6, 5, 6};
//     vector<int> a2 = {1, 2};
//     vector<int> b2 = {2, 3};
//     vector<vector<int>> tari = create_map(6, 9, a, b);

//     for(int i = 0; i < 12; i++){
//         for(int j = 0; j < 12; j++){
//             cout << tari[i][j] << " ";
//         }
//         cout << endl;
//     }
// }

• 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