Submission #1250953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250953		lukameladze	World Map (IOI25_worldmap)	C++20	58 / 100	167 ms	20212 KiB

worldmap

#include "worldmap.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <iostream>
#define pb push_back
using namespace std;
const int MX = 1005;
vector <int> v[MX], be[MX], de[MX];
vector <int> ord;
void dfs(int a, int p, vector<int> &fix) {
    fix[a] = 1;
    ord.pb(a);
    for (int to : v[a]) {
        if (to == p) continue;
        if (fix[to]) {
            be[a].pb(to);
        } else {
            de[a].pb(to);
            dfs(to, a, fix);
             ord.pb(a);
        }
        

    }
   
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
    int n = N;
    ord.clear();
    vector <int> fix(n + 1, 0);
    for (int i = 0; i <= N; i++) {
        fix[i] = 0;
        v[i].clear();
        be[i].clear();
        de[i].clear();
    }
    for (int i = 0; i < M; i++) {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
    }
    dfs(1, 0, fix);
    vector <vector<int>> ans;
    
    ans.clear();
    for (int i = 0; i < ord.size(); i++) {
        vector <int> vec;
        for (int j = 0; j < ord.size(); j++) {
            vec.pb(ord[i]);
        }
        ans.pb(vec);
    }
    vector <vector <int>> res;
    for (int i = 0; i < ord.size(); i++) {
        res.pb(ans[i]);
        int vert = ord[i];
        if (be[vert].size()) {
            vector <int> vec;
            for (int j = 0; j < be[vert].size(); j++) {
                vec.pb(be[vert][j]);
                vec.pb(vert);
            }
            res.pb(vec);
            vec.clear();
            for(int i = 0; i < ord.size(); i++) {
                vec.pb(vert);
            }
            res.pb(vec);
        }
    }
    int sz = res.size();
    for (int i = 0; i < sz; i++) {
        while (res[i].size() < sz) {
            res[i].pb(res[i].back());
        }
    }
    return res;

}

• 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: 14 / 56