Submission #941699

#	Time	Username	Problem	Language	Result	Execution time	Memory
941699		vjudge1	City Mapping (NOI18_citymapping)	C++17	100 / 100	22 ms	8544 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
    int a,b,w;
};
int d[1001][1001],h[1001],deg[1001];
vector <edge> res;
vector <pair <int, int>> tmp;
vector <int> ve[1001];
vector <pair <int, int>> ke[1001];
map <int, int> mp;
int get(int i, int j){
    if (i==j)
        return 0;
    if (i>j)
        swap(i,j);
    if (d[i][j])
        return d[i][j];
    return d[i][j]=get_distance(i,j);
}
void addEdge(int a, int b, int w){
    deg[a]++;
    deg[b]++;
    res.push_back({a,b,w});
}
void dfs(int u, int p, int root, int cur=0){
    d[root][u]=d[u][root]=cur;
    for (auto [v,w]:ke[u])
        if (v!=p)
            dfs(v,u,root,cur+w);
}
void solve(int x){
    sort(ve[x].begin(),ve[x].end(),[](int i, int j){return h[i]<h[j];});
    addEdge(x,ve[x][0],h[ve[x][0]]);
    for (int i=1;i<ve[x].size();i++){
        vector <pair <int, int>> c;
        int u=ve[x][i];
        for (int j=i-1;j>=0;j--)
            if (deg[ve[x][j]]<3&&h[u]>h[ve[x][j]])
                c.push_back({ve[x][j],h[u]-h[ve[x][j]]});
        while (c.size()>1){
            int val=get(c[0].first,u);
            vector <pair <int, int>> c2;
            for (auto [i,j]:c)
                if (get(c[0].first,i)+j==val)
                    c2.push_back({i,j});
            swap(c,c2);
        }
        auto [v,w]=c[0];
        addEdge(u,v,w);
        ke[u].push_back({v,w});
        ke[v].push_back({u,w});
        dfs(u,u,u);
    }
}
void find_roads(int32_t n, int32_t Q, int32_t A[], int32_t B[], int32_t W[]){
    int a=1,b=1,mx=0;
    for (int i=2;i<=n;i++)
        if (mx<get(1,i)){
            a=i;
            mx=get(1,i);
        }
    mx=0;
    for (int i=1;i<=n;i++)
        if (mx<get(a,i)){
            b=i;
            mx=get(a,i);
        }
    for (int i=1;i<=n;i++)
        if (get(a,i)+get(i,b)==get(a,b)){
            tmp.push_back({get(a,i),i});
            mp[get(a,i)]=i;
        }
    sort(tmp.begin(),tmp.end());
    for (int i=0;i+1<tmp.size();i++)
        addEdge(tmp[i].second,tmp[i+1].second,tmp[i+1].first-tmp[i].first);
    for (int i=1;i<=n;i++){
        int da=(get(a,b)+get(a,i)-get(b,i))/2;
        h[i]=(get(a,i)+get(b,i)-get(a,b))/2;
        if (mp[da]!=i)
            ve[mp[da]].push_back(i);
    }
    for (int i=1;i<=n;i++)
        if (!ve[i].empty())
            solve(i);
    for (int i=0;i<n-1;i++){
        A[i]=res[i].a;
        B[i]=res[i].b;
        W[i]=res[i].w;
    }
}

Compilation message (stderr)

citymapping.cpp: In function 'void solve(long long int)':
citymapping.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=1;i<ve[x].size();i++){
      |                  ~^~~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int32_t, int32_t, int32_t*, int32_t*, int32_t*)':
citymapping.cpp:77:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i=0;i+1<tmp.size();i++)
      |                  ~~~^~~~~~~~~~~

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