Submission #1134744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134744		Aviansh	City Mapping (NOI18_citymapping)	C++20	25 / 100	423 ms	41644 KiB

citymapping

#include "citymapping.h"

#include <bits/stdc++.h>

using namespace std;

void find_roads(int n, int q, int a[], int b[], int w[]) {
    vector<array<long long,2>>g[n];
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            long long dist = get_distance(i+1,j+1);
            g[i].push_back({j,dist});
            g[j].push_back({i,dist});
        }
    }
    priority_queue<array<long long,3>,vector<array<long long,3>>,greater<array<long long,3>>>pq;
    bool vis[n];
    fill(vis,vis+n,0);
    for(array<long long,2>e:g[0]){
        //cout << "pushed1: " << e[1] << " " << 0 << " " << e[0] << endl;
        pq.push({e[1],0,e[0]});
    }
    vis[0]=1;
    int ind = 0;
    while(!pq.empty()){
        array<long long,3>e = pq.top();
        pq.pop();
        if(vis[e[2]])
            continue;
        vis[e[2]]=1;
        a[ind]=e[1]+1;
        b[ind]=e[2]+1;
        w[ind]=e[0];
        ind++;
        for(array<long long,2>a:g[e[2]]){
            //cout << "pushed2: " << a[1] << " " << e[2] << " " << a[1] << endl;
            pq.push({a[1],e[2],a[0]});
        }
    }
	return;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 43