Submission #1117982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117982		trinhvtuan	Cities (BOI16_cities)	C++17	0 / 100	160 ms	59048 KiB

cities

#include <bits/stdc++.h>
using namespace std;
long long c,d,x,y,z,n,id,m;
int i,j,k;
typedef pair<long long,int>i2;
typedef pair<long long,i2>i3;
vector<i3>b;
vector<int>q;
vector<i2>a[1000001];
long long h[1000001],up[200005][22],s[1000001],en[1000001],p[1000001],g[1000001];
bool cmp(int x,int y)
{
    if (s[x]<s[y]) return true;
    return false;
}
int dsu(int u)
{
    if (u==p[u]) return u;
    return p[u]=dsu(p[u]);
}
void dfs(int u)
{
    id++; s[u]=id;
    for (int i=0;i<a[u].size();i++)
    {
        int v=a[u][i].second;
        if (v==up[u][0]) continue;
        h[v]=h[u]+1;
        g[v]=g[u]+a[u][i].first;
        up[v][0]=u;
        for (int j=1;j<=20;j++)
        up[v][j]=up[up[v][j-1]][j-1];
        dfs(v);
    }
    en[id]=u;
}
int lca(int u,int v)
{
    if (h[u]!=h[v])
    {
        if (h[u]<h[v]) swap(u,v);
        int k=h[u]-h[v];
        for (int j=0;(1<<j)<=k;j++)
        if (k>>j&1) u=up[u][j];
    }
    if (u==v) return u;
    int k=__lg(h[u]);
    for (int j=k;j>=0;j--)
    if (up[u][j]!=up[v][j])
    {
        u=up[u][j]; v=up[v][j];
    }
    return up[u][0];
}
long long dist(int u,int v)
{
    int c=lca(u,v);
    return g[u]+g[v]-2*g[c];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>k>>m;
    for (int i=1;i<=n;i++)
    p[i]=i;
    for (int i=1;i<=k;i++)
    {
        cin>>x; q.push_back(x);
    }
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        b.push_back({z,{x,y}});
    }
    sort(b.begin(),b.end());
    for (int i=0;i<b.size();i++)
    {
        int u=b[i].second.first; int v=b[i].second.second;
        z=b[i].first;
        x=dsu(u); y=dsu(v);
        if (x!=y)
        {
            if (x>y) swap(x,y);
            p[y]=x;
            a[u].push_back({z,v});
            a[v].push_back({z,u});
            //cout<<u<<" "<<v<<" "<<z<<"\n";
        }
    }
    dfs(1);
    sort(q.begin(),q.end(),cmp);
    for (int i=1;i<q.size();i++)
    {
        int u=q[i]; int v=q[i-1];
        c+=dist(u,v);
    }
    c+=dist(q[0],q[q.size()-1]);
    cout<<c/2;
}

Compilation message (stderr)

cities.cpp: In function 'void dfs(int)':
cities.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i=0;i<a[u].size();i++)
      |                  ~^~~~~~~~~~~~
cities.cpp: In function 'int main()':
cities.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i=0;i<b.size();i++)
      |                  ~^~~~~~~~~
cities.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i=1;i<q.size();i++)
      |                  ~^~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26