Submission #1283775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283775		janson0109	World Map (IOI25_worldmap)	C++20	12 / 100	10 ms	2104 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 998244353;

void dfs(vector<vector<ll>> &e, ll root, vector<bool> &vis, vector<ll> &tour) {
    vis[root] = 1;
    tour.push_back(root);
    for(auto & v : e[root]) if(!vis[v]) dfs(e, v, vis, tour);
    tour.push_back(root);
}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
    vector<vector<ll>> e(N);
    for(ll i=0; i<M; i++) {e[A[i]-1].push_back(B[i]-1); e[B[i]-1].push_back(A[i]-1);}
    vector<bool> vis(N,0); vector<ll> tour;
    dfs(e, 0, vis, tour);
    tour.pop_back();
    vector<ll> sz, pos(N); vector<bool> used(N,0);
    vector<ll> sum = {0};
    for(auto & x : tour) {
        sz.push_back(used[x] ? 1 : 3);
        sum.push_back(sum.back()+ sz.back());
        if(!used[x]) pos[x] = sum.back() - 2;
        used[x] = 1;
    }
    vector<pair<ll,ll>> ord;
    for(ll i=0; i<N; i++) ord.push_back(make_pair(min(pos[i], 4*N-pos[i]), i));
    sort(ord.begin(), ord.end());
    map<ll,ll> place;
    for(ll i=0; i<N; i++) place[ord[i].S] = i;
    vector<vector<ll>> ins(N);
    for(ll i=0; i<M; i++) {
        ll a = A[i]-1, b = B[i]-1;
        if(place[a] > place[b]) swap(a,b);
        ins[b].push_back(a);
    }
    
    vector<vector<int>> ans(2*N, vector<int>(2*N));
    for(ll i=0; i<2*N-1; i++) {
        for(ll j=sum[i]; j<sum[i+1]; j++) {
            for(ll k=0; k<2*N; k++) if(j-k < 2*N && j-k >= 0) {
                ans[k][j-k] = tour[i]+1;
            }
        }
    }
    for(ll i=0; i<N; i++) {
        ll cnt = 0;
        for(ll j=0; j<2*N; j++) if(pos[i] - j < 2*N && pos[i] - j >= 0) {
            if(cnt < ins[i].size()) ans[j][pos[i] - j] = ins[i][cnt] + 1;
            cnt++;
        }
    }
    return ans;
}

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