Submission #1260212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260212		software1146	World Map (IOI25_worldmap)	C++17	100 / 100	21 ms	2888 KiB

worldmap

#include "worldmap.h"

#include <bits/stdc++.h>

using namespace std;

void dfs(int st, vector<int>g[], bool vis[], vector<vector<int>> &ans, int &sm, int n){
    vis[st]=1;
    vector<int>anc;
    for(int i : g[st]){
        if(vis[i]){
            anc.push_back(i);
        }
    }
    for(int i = 0;i<=sm;i++){
        int j = sm-i;
        if(i>=n||j>=n)
            continue;
        ans[i][j]=st;
    }
    sm++;
    if(anc.size()){
        int in = 0;
        for(int i = 0;i<=sm;i++){
            int j = sm-i;
            if(i>=n||j>=n)
                continue;
            ans[i][j]=anc[min(in,(int)anc.size()-1)];
            in++;
        }
        sm++;
        for(int i = 0;i<=sm;i++){
            int j = sm-i;
            if(i>=n||j>=n)
                continue;
            ans[i][j]=st;
        }
        sm++;
    }
    for(int i : g[st]){
        if(vis[i])
            continue;
        dfs(i,g,vis,ans,sm,n);
        for(int i = 0;i<=sm;i++){
            int j = sm-i;
            if(i>=n||j>=n)
                continue;
            ans[i][j]=st;
        }
        sm++;
    }
}

vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) {
    vector<int>g[n];
    for(int i = 0;i<m;i++){
        A[i]--;
        B[i]--;
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    bool vis[n];
    fill(vis,vis+n,0);
    vector<vector<int>>ans(2*n-1,vector<int>(2*n-1,-1));
    int t = 0;
    dfs(0,g,vis,ans,t,2*n-1);
    for(int i = 0;i<2*n-1;i++){
        for(int j = 0;j<2*n-1;j++){
            ans[i][j]++;
        }
    }
    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