Submission #1253208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253208		idiotcomputer	World Map (IOI25_worldmap)	C++20	100 / 100	21 ms	2888 KiB

worldmap

//IOI 2025 Day 1 Problem C 

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define sz(x) (int) (x).size()
#define vi vector<int>
#define f first
#define s second 
#include "worldmap.h"

const int mxN = 45;
int n;

vi adj[mxN];
int first[mxN];
bool vis[mxN];
vi ord;

void dfs(int node, int p){
    vis[node] = 1;
    first[node] = sz(ord);
    ord.pb(node);
    for (int i : adj[node]){
        if (i == p || vis[i]) continue;
        dfs(i,node);
        ord.pb(node);
    }
}



vector<vi> create_map(int N, int m, vi a, vi b){
    n = N;
    for (int i = 0; i < n; i++) adj[i].clear(),vis[i]=0;
    for (int i = 0; i < m; i++) adj[a[i]-1].pb(b[i]-1), adj[b[i]-1].pb(a[i]-1);

    ord.clear();
    dfs(0,-1);

    vector<vi> grid(2*n);
    for (int i = 0; i < 2*n; i++) grid[i].resize(2*n);

    //for (int i = 0; i < n; i++) cout << first[i] << " ";
    //cout << '\n';
    //for (int i : ord) cout << i << " ";
    //cout << '\n';
    //return grid;

    int idx[n];
    memset(idx,0,sizeof(idx));
    int cnt = 1;
    int l = 0;
    int r = sz(ord)-1;
    while (l <= r){
        if (idx[ord[l]] == 0) idx[ord[l]] = cnt, cnt++;
        l++;
        if (l > r) break;
        if (idx[ord[r]] == 0) idx[ord[r]] = cnt, cnt++;
        r--;
    }
    //for (int i = 0; i < n; i++) cout << idx[i] << " ";
    //cout << "\n\n";
    //return grid;
    l = 0;
    //ord.pop_back();
    for (int i = 0; i < sz(ord); i++){
        int c = ord[i];
        int mj = max(l-2*n+1,0);
        for (int j = mj; j <= min(2*n-1,l); j++) grid[j][l-j] = c+1;
        l++;
        if (first[c] == i){
            //add in adj
            mj = max(l-2*n+1,0);
            for (int j = mj; j <= min(2*n-1,l); j++) grid[j][l-j] = c+1;
            int cj = 0;
            for (int i : adj[c]) if (idx[i] < idx[c]) grid[mj+cj][l-cj-mj] = i+1, cj++;
            l++;
            mj = max(l-2*n+1,0);
            for (int j = mj; j <= min(2*n-1,l); j++) grid[j][l-j] = c+1;
            l++;
        }
    }
    return grid;
}

/*
int main() {
  int T;
  assert(1 == scanf("%d", &T));

  std::vector<int> Nt(T), Mt(T);
  std::vector<std::pair<std::vector<int>, std::vector<int>>> AB;

  for (int t = 0; t < T; ++t) {
    assert(2 == scanf("%d %d", &Nt[t], &Mt[t]));

    int M = Mt[t];
    std::vector<int> A(M), B(M);

    for (int i = 0; i < Mt[t]; i++) {
      assert(2 == scanf("%d %d", &A[i], &B[i]));
    }
    AB.push_back(make_pair(A, B));
  }

  fclose(stdin);

  std::vector<std::vector<std::vector<int>>> Ct;

  for (int t = 0; t < T; t++) {
    int N = Nt[t], M = Mt[t];
    std::vector<int> A = AB[t].first, B = AB[t].second;

    auto C = create_map(N, M, A, B);
    Ct.push_back(C);
  }

  for (int t = 0; t < T; t++) {
    auto& C = Ct[t];
    int P = (int)C.size();

    std::vector<int> Q(P);
    for (int i = 0; i < P; ++i)
      Q[i] = (int)C[i].size();

    printf("%d\n", P);
    for (int i = 0; i < P; ++i)
      printf("%d%c", Q[i], " \n"[i + 1 == P]);
    printf("\n");
    for (int i = 0; i < P; i++) {
      for (int j = 0; j < Q[i]; j++) {
        printf("%d%c", C[i][j], " \n"[j + 1 == Q[i]]);
      }
    }
    if (t < T - 1)
      printf("\n");
  }

  fclose(stdout);

  return 0;
}*/

• 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