Submission #1261304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261304		Samuraj	World Map (IOI25_worldmap)	C++20	86 / 100	46 ms	5704 KiB

worldmap

#include <bits/stdc++.h>
#include "worldmap.h"

using namespace std;

#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi; 
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;

const int max_n = 50;
vi g[max_n];
int h[max_n];
int s[max_n];
//bool leaf[max_n];
int arr[max_n*3][max_n*3];

void set_tree(int v){
    //cout << "set_tree, v: " << v << " h: " << h[v] << '\n';
    s[v] = 1;   
    //leaf[v] = 1;
    for(auto x:g[v]){
        //cout << "v: " << v << " x: " << x << '\n';  
        if(h[x]) continue;
        //leaf[v] = 0;
        h[x] = h[v]+1;
        set_tree(x);
        s[v] += s[x];
    }
    //cout << "v: " << v << " s: " << s[v] << '\n';
}

void solve(int v, int i, int j){
    
    /* if(leaf[v]){
        cout << "leaf\n";
        return;
    } */
    int end = j+3*s[v]-2; //raz -1 bierzemy od size-1 jako placeholder!
    //cout << "\nsolve od v: " << v << " i: " << i << " j: " << j << " end: " << end << '\n';
    rep(it,j,end) arr[i][it] = v; //pierwszy rzad same 1!

    //tutaj placeholder niepotrzebne!
    int l = j+1;
    for(auto x:g[v]){
        if(h[x] < h[v]) continue; //nie dajemy kolejnych
        arr[i+1][l] = x; arr[i+1][l+1] = v;
        l += 2;
    }
    arr[i+1][j] = v;
    rep(it,l,end) arr[i+1][it] = v;

    rep(it,j,end) arr[i+2][it] = v; //ostatni to samo!

    //teraz solve na kolejne :)
    //tutaj placeholder!
    arr[i+3][j] = v; //ten najbardziej po lewo!
    l = j+1; //nastepne od ktorego zaczynamy
    for(auto x:g[v]){
        if(h[x] != h[v]+1) continue;
        solve(x,i+3,l);
        l += 3*s[x];
        arr[i+3][l-1] = v;
    }
    rep(it,l,j) arr[i+3][it] = v;
}

vector<vi> create_map(int n, int m, vi a, vi b){

   /*  cout << "\n\nnowy test\n";
    rep(i,1,n)
        cout << "i: " << i << " size: " << g[i].size() << " h: " << h[i] << " s: " << s[i] << '\n';
    cout << "arr\n";
    rep(i,1,n){
        rep(j,1,n) cout << arr[i][j] << ' ';
        cout << '\n';
    } */

    //na 86 :)
    rep(i,0,m-1){
        int x = a[i]; int y = b[i];
        g[x].pb(y); g[y].pb(x);
        //cout << "set_g, x: " << x << " y: " << y << '\n';
    }
    h[1] = 1;
    set_tree(1);

    solve(1,1,1);
    rep(i,1,3*n)
        rep(j,1,3*n){
            if(arr[i][j]) continue;
            if(i == 1) arr[i][j] = 1;
            else arr[i][j] = arr[i-1][j];
        }
    
    vector<vi> ans;
    rep(i,1,3*n){
        vi v;
        rep(j,1,3*n) v.pb(arr[i][j]);
        ans.pb(v);
    }

    rep(i,1,max_n-1){
        g[i].clear();
        h[i] = 0;
        s[i] = 0;
    }
    rep(i,1,3*max_n-1) rep(j,1,3*max_n-1) arr[i][j] = 0;

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