Submission #220889

#	Time	Username	Problem	Language	Result	Execution time	Memory
220889		Ruxandra985	Cities (BOI16_cities)	C++14	0 / 100	157 ms	10656 KiB

cities

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int tt[DIMN] , sp[DIMN] , f[DIMN];
pair <int,int> fth[DIMN];
int lvl[DIMN];
vector <pair <int,int> > w[DIMN];
pair <int , pair <int,int> > v[2 * DIMN];
int root (int x){

    while (tt[x] > 0)
        x = tt[x];

    return x;

}

void dfs (int nod){
    int i , vecin;



    for (i = 0 ; i < w[nod].size() ; i++){
        vecin = w[nod][i].first;
        if (vecin != fth[nod].first){
            fth[vecin] = make_pair(nod , w[nod][i].second);
            lvl[vecin] = 1 + lvl[nod];
            dfs (vecin);
        }
    }

}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , k , i , x , y , rx , ry , cost , nod , lca , lmax;
    long long sum = 0;
    fscanf (fin,"%d%d%d",&n,&k,&m);

    for (i = 1 ; i <= k ; i++)
        fscanf (fin,"%d",&sp[i]);

    for (i = 1 ; i <= m ; i++)
        fscanf (fin,"%d%d%d",&v[i].second.first , &v[i].second.second , &v[i].first);

    sort (v + 1 , v + m + 1);

    for (i = 1 ; i <= n ; i++)
        tt[i] = -1;

    for (i = 1 ; i <= m ; i++){
        x = v[i].second.first;
        y = v[i].second.second;
        cost = v[i].first;

        rx = root(x);
        ry = root(y);

        if (rx != ry){

            w[x].push_back(make_pair(y , cost));
            w[y].push_back(make_pair(x , cost));

            if (tt[rx] < tt[ry]){
                tt[rx] += tt[ry];
                tt[ry] = rx;
            }
            else {
                tt[ry] += tt[rx];
                tt[rx] = ry;
            }

        }

    }
    /// am apm ul , vreau surbarborele minim care contine toate cele 5 noduri

    dfs (1);

    for (i = 1 ; i <= k ; i++){
        nod = sp[i];

        while (nod){
            f[nod]++;
            nod = fth[nod].first;
        }

    }

    lca = 0;
    lmax = -1;

    for (i = 1 ; i <= n ; i++){
        if (f[i] == k && lmax < lvl[i]){
            lmax = lvl[i];
            lca = i;
        }
    }

    for (i = 1 ; i <= k ; i++){
        nod = sp[i];

        while (nod != lca){
            sum += fth[nod].second;
            nod = fth[nod].first;
        }

    }

    fprintf (fout,"%lld",sum);
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'void dfs(int)':
cities.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < w[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
cities.cpp: In function 'int main()':
cities.cpp:40:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&k,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:43:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&sp[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~
cities.cpp:46:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d%d",&v[i].second.first , &v[i].second.second , &v[i].first);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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