Submission #1250616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250616		NekoRolly	World Map (IOI25_worldmap)	C++20	72 / 100	71 ms	9284 KiB

worldmap

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

const int N = 44;

int n,m;
vector<int> adj[N];
int vis[N];
vector<vector<int>> rec;

void dfs(int u,int p){
    // cout << "u :" << u << "\n";
    rec.push_back({u});
    vis[u] = 1;
    vector<int> vec; // back edges
    for (int v : adj[u]){
        if (v == p) continue;
        if (vis[v] == 1)
            vec.push_back(v);
        if (vis[v] == 0){
            dfs(v, u);
            rec.push_back({u});
        }
    }
    vis[u] = 2;
    if (vec.empty()) return;
    vector<int> vec1,vec2;
    vec1 = vec2 = {u};
    for (int v : vec){
        vec1.push_back(v);
        vec1.push_back(u);
        vec2.push_back(u);
        vec2.push_back(u);
    }
    rec.push_back(vec1);
    rec.push_back(vec2);
}

vector<vector<int>> create_map(int N,int M,vector<int> A,vector<int> B) {
    n = N, m = M;

    for (int i=1; i<=n; i++){
        adj[i].clear();
        vis[i] = 0;
    }
    rec.clear();

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

    dfs(1, -1);

    int k = rec.size();
    for (auto &vec : rec){
        while (vec.size() < k)
            vec.push_back(vec.back());
    }

    return rec;
}

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