Submission #1264363

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

worldmap

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

void prv(vector<int> &v) {
    for (auto i:v) {
        cout << i <<" ";
    }
    cout << endl;
}

vector<vector<int>> adjlist;
int n,m;

vector<int> visited;
vector<int> tour;
void dfs(int node) {
    tour.push_back(node);
    visited[node] = 1;
    for (int j:adjlist[node]) {
        if (!visited[j]) {
            dfs(j);
            tour.push_back(node);
        }
    }
}


vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    n=N; m=M;
    int width = 4*n;
    vector<vector<int>> ans(width, vector<int>(width, -1));
    visited=vector<int>(n,0);
    adjlist=vector<vector<int>>(n);
    for (int i=0; i<m; i++) {
        adjlist[A[i]-1].push_back(B[i]-1);
        adjlist[B[i]-1].push_back(A[i]-1);
    }
    dfs(0);
    //cout << "TOURSIZE" <<" " << tour.size() << endl;
    //prv(tour);
    int rowpointer = 0;
    vector<int> seen(n,0);
    for (int col:tour) {
        if (!seen[col]) {
            for (int i=0; i<width; i++) {
                ans[rowpointer][i] = col;
            }
            rowpointer++;
            for (int i=0; i<width; i++) {
                ans[rowpointer][i] = col;
            }
            for (int i=0; i<adjlist[col].size(); i++) {
                assert(2*i<width);
                //cout << tour.size() <<" " << i <<" " << col <<" " << rowpointer << " " << width << " " << n <<" " << endl;
                assert(rowpointer<width);
                ans[rowpointer][i] = adjlist[col][i];
            }
            rowpointer++;
            for (int i=0; i<width; i++) {
                ans[rowpointer][i] = col;
            }
            rowpointer++;
        }
        else {
            //seen before so just do 1 line
            for (int i=0; i<width; i++) {
                ans[rowpointer][i] = col;
            }
            rowpointer++;
        }
        seen[col] = 1;
    }
    while (rowpointer<width) {
        //cout << rowpointer <<" " << tour.back() <<" " << ans.size() << endl;
        for (int i=0; i<width; i++) {
            ans[rowpointer][i] = tour.back();
        }
        rowpointer++;
    }
    vector<vector<int>> finalans(3*n, vector<int>(3*n,-1));
    for (int i=0; i<4*n; i++) {
        //the diagonal with sums i+n
        vector<int> cords;
        for (int x=0; x<3*n; x++) {
            int y = i+n-x;
            if (0<=y && y<3*n) {
                cords.push_back(x);
            }
        }
        for (int j=0; j<cords.size(); j++) {
            finalans[i+n-cords[j]][cords[j]] = ans[i][j];
        }
    }
    for (int i=0; i<n*3; i++) {
        for (int j=0; j<3*n; j++) {
            if (finalans[i][j]==-1) {
                if (i>0 && finalans[i-1][j]!=-1) finalans[i][j] = finalans[i-1][j];
                if (j>0 && finalans[i][j-1]!=-1) finalans[i][j] = finalans[i][j-1];
            }
        }
    }
    for (int i=n*3-1; i>=0; i--) {
        for (int j=3*n-1; j>=0; j--) {
            if (finalans[i][j]==-1) {
                if (i<3*n-1 && finalans[i+1][j]!=-1) finalans[i][j] = finalans[i+1][j];
                if (j<3*n-1 && finalans[i][j+1]!=-1) finalans[i][j] = finalans[i][j+1];
            }
        }
    }
    for (int i=0; i<3*n; i++) {
        for (int j=0; j<3*n; j++) {
            finalans[i][j]++;
        }
    }
    tour.clear();
    return finalans;
}

• 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