| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1259177 | SalihSahin | City Mapping (NOI18_citymapping) | C++20 | 0 ms | 0 KiB |
#include "city_mapping.h"
#include <bits/stdc++.h>
using namespace std;
#define heps(v) v.begin(), v.end()
typedef long long int lli;
typedef pair<lli,lli> plli;
typedef vector<lli> vlli;
typedef vector<plli> vplli;
typedef pair<lli,plli> pplli;
typedef vector<pplli> vpplli;
lli n,m,k,q,t;
lli uzak[1002][1002];
lli cev[1002][1002];
void coz(vlli vect, lli root){
vplli uzvect;
for(lli say : vect){
uzvect.push_back({uzak[root][say], say});
}
sort(heps(uzvect));
cev[uzvect[0].second][root] = uzvect[0].first;
if(uzvect.size() <= 1)
return;
plli med = uzvect[uzvect.size() / 2];
for(lli say : vect){
if(say == med.second)
continue;
uzak[med.second][say] = get_distance(med.second, say);
}
//cout << "burada " << root << " " << vect.size() << endl;
vlli digvect;
plli ens = {0,root};
map<lli,vlli> rootma;
map<lli,lli> arfar;
vlli arvect;
for(plli say : uzvect){
lli meduz = uzak[med.second][say.second];
if(say.first == meduz - med.first)
digvect.push_back(say.second);
else if(say.first == med.first - meduz){
cev[say.second][ens.second] = say.first - ens.first;
arfar[say.first - meduz] = say.second;
arvect.push_back(say.second);
ens = say;
}
else{
lli fa = say.first - meduz;
rootma[arfar[fa]].push_back(say.second);
uzak[arfar[fa]][say.second] = say.first - uzak[root][arfar[fa]];
}
}
//cout << "ciktiloop " << root << endl;
if(!digvect.empty())
coz(digvect, root);
for(lli par : arvect){
if(!rootma[par].empty())
coz(rootma[par], par);
}
}
vpplli kenarlar;
void find_roads(int n, int q, int a[], int b[], int c[]){
lli root = 1;
vlli vect;
for(lli i = 1;i<=n;i++){
if(i == root)
continue;
uzak[root][i] = get_distance(root, i);
vect.push_back(i);
}
//cout << "burada4" << endl;
coz(vect, root);
//cout << "burada3" << endl;
for(lli i = 1;i<=n;i++){
for(lli j = i + 1;j<=n;j++){
if(cev[i][j] || cev[j][i])
kenarlar.push_back({max(cev[i][j], cev[j][i]), {i,j}});
}
}
//cout << "burada2" << endl;
for(lli i = 0;i<kenarlar.size();i++){
a[i] = kenarlar[i].second.first;
b[i] = kenarlar[i].second.second;
c[i] = kenarlar[i].first;
}
}