Submission #1323976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323976		ZeroCool	World Map (IOI25_worldmap)	C++20	100 / 100	23 ms	2944 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
#define ar array
#define all(v) v.begin(), v.end()

using namespace std;
const int N = 50;

vector<int> g[N];
vector<int> ord;

bool vis[N];

set<ar<int,2> > e;


int dep[N];
void dfs(int x){
    vis[x] = 1;
    // cout<<x<<" ";
    for(auto u: g[x]){
        if(vis[u])continue;
        ord.push_back(x);
        dep[u] = dep[x] + 1;
        e.erase({min(u, x), max(u, x)});
        dfs(u);
    }
    ord.push_back(x);
}   

std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> A, std::vector<int> B) {
    for(int i = 1;i <= n;i++)g[i].clear(), vis[i] = 0;
    e.clear();
    ord.clear();
    for(int i = 0;i < m;i++){
        auto [a, b] = ar<int,2>{A[i], B[i]};
        g[a].push_back(b);
        g[b].push_back(a);
        // cout<<a<<" "<<b<<endl;
        e.insert({min(a, b), max(a, b)});
    }
    dfs(1);
    // cout<<endl;
    int k = 2 * n;
    vector<vector<int> > ans(k, vector<int>(k, -1));
    vector<int> f[n + 1];
    for(auto [a, b]: e){
        if(dep[a] < dep[b])swap(a, b);
        f[a].push_back(b);
    }
    vector<ar<int,2>> D[2 * k -1];
    for(int i = 0;i < k;i++){
        for(int j = 0;j < k;j++)D[i + j].push_back({i, j});
    }
    // for(auto u: ord)cout<<u<<" ";
    // cout<<endl;
    // assert(0);
    set<int> s;
    int d = 0;
    for(auto u: ord){
        if(s.count(u)){
            for(auto [a, b]: D[d])ans[a][b] = u;
            d++;
            continue;
        }
        s.insert(u);
        for(auto [a, b]: D[d])ans[a][b] = u;
        d++;
        for(auto [a, b]: D[d])ans[a][b] = u;
        // cout<<D[d].size()<<" "<<f[u].size()<<'\n';
        for(int i = 0;i < f[u].size();i++){
            auto [a, b] = D[d][i];
            ans[a][b] = f[u][i];
        }
        d++;
        for(auto [a, b]: D[d])ans[a][b] = u;
        d++;
    }

    for(;d < 2 * k - 1;d++){
        for(auto [a, b]: D[d])ans[a][b] = 1;
    }
    return ans;
}

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