Submission #1264358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264358		anango	World Map (IOI25_worldmap)	C++20	72 / 100	73 ms	9544 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][2*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++;
    }
    for (int i=0; i<width; i++) {
        for (int j=0; j<width; j++) {
            ans[i][j]++;
        }
    }
    tour.clear();
    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: 28 / 56