Submission #1257802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257802		Rainmaker2627	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	328 KiB

worldmap

#include "worldmap.h"

int n, dcnt=0;
std::vector<int> vis;
std::vector<std::vector<int>> child, back, adj, ans;
void fill_diag(int d, int c) {
    for (int x = 0; x < 2*n; x++) {
        int y=d-x;
        if (0<=y && y<2*n) ans[x][y]=c; 
    }
}

void dfs(int u, int p, int t=1) {
    vis[u]=t;
    int diag=dcnt+1; dcnt+=3;
    fill_diag(diag-1, u);
    fill_diag(diag, u);
    fill_diag(diag+1, u);
    int x=std::max(0, diag-2*n+1);
    for (auto v : adj[u]) {
        if (v==p) continue;
        if (!vis[v]) {
            dfs(v, u, t+1);
            fill_diag(dcnt, v);
            dcnt++;
        } else if (vis[v]<vis[u]) {
            ans[x][diag-x]=v;
            x++;
        }
    }
}

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

    child.assign(N+1, std::vector<int>());
    back.assign(N+1, std::vector<int>());
    adj.assign(N+1, std::vector<int>());
    vis.assign(N+1, 0);
    for (int i = 0; i < M; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    
    ans.assign(2*N, std::vector<int>(2*N, 1));
    dfs(1, 1);

    return ans;
}

• 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