Submission #1279862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279862		Andrey	World Map (IOI25_worldmap)	C++20	22 / 100	14 ms	3268 KiB

worldmap

#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;

int n;
int m;
int k;
vector<int> haha[100];
vector<int> st(100);
vector<vector<int>> ans(0);
vector<int> tree[100];
vector<int> banana[100];
vector<int> dep(100);
vector<bool> bruh(100);

void reset() {
    for(int i = 0; i < 100; i++) {
        haha[i].clear();
        tree[i].clear();
        banana[i].clear();
        bruh[i] = true;
        dep[i] = -1;
    }
    ans.clear();
}

void dfs(int a, int d) {
    st[a] = 1;
    dep[a] = d;
    bruh[a] = false;
    for(int v: haha[a]) {
        if(bruh[v]) {
            tree[a].push_back(v);
            dfs(v,d+1);
            st[a]+=st[v];
        }
        else if(dep[v] > dep[a]) {
            banana[a].push_back(v);
        }
    }
}

void no(int i, int y, int c) {
    for(int j = y; j < k; j++) {
        ans[j][i] = c;
    }
}

void dude(int x, int y, int a, int w) {
    if(st[a] == 1) {
        for(int i = y; i < k; i++) {
            for(int j = x; j < x+w; j++) {
                ans[i][j] = a;
            }
        }
        return;
    }
    for(int i = 0; i < 2; i++) {
        for(int j = x; j < x+w; j++) {
            ans[y+i][j] = a;
        }
    }
    no(x,y,a);
    int z = x+1;
    for(int v: tree[a]) {
        dude(z,y+2,v,st[v]*2-1);
        z+=st[v]*2;
        no(z-1,y,a);
    }
    int c = x+1;
    if(c%2) {
        c++;
    }
    int q = 0;
    for(int i = c; i < x+w-1; i+=2) {
        if(q < banana[a].size()) {
            ans[y+1][i] = banana[a][q];
            ans[y+2][i] = a;
            q++;
        }
    }
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    reset();
    n = N;
    m = M;
    for(int i = 0; i < m; i++) {
        haha[A[i]].push_back(B[i]);
        haha[B[i]].push_back(A[i]);
    }
    k = 2*n-1;
    for(int i = 0; i < k; i++) {
        ans.push_back(vector<int> (k));
    }
    dfs(1,0);
    dude(0,0,1,k);
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56