Submission #21908

#	Time	Username	Problem	Language	Result	Execution time	Memory
21908		iletavcioski	Cities (BOI16_cities)	C++14	0 / 100	249 ms	14440 KiB

cities

#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
typedef long long ll;
bool oznaceni[100001];
struct node
{
   int a,b;
   ll val;
};
const bool operator <(const node &x,const node&y)
{
    return x.val>y.val;
}
vector<int> p(100001,-1);
vector<int> d(100001,0);
int dsu(int a)
{
    if(p[a]==-1)
        return a;
    return dsu(p[a]);
}
void dsu1(int a,int b)
{
    if(p[a]!=b)
    {
       dsu1(p[a],b);
       p[a]=b;
    }
    else
        return;
}
vector<vector<pair<int,ll> > > v;
pair<ll,bool> dfs(int x,int prev)
{
    ll brojac=0;
    bool cc=false;
    for(int i=0;i<v[x].size();i++)
    {
        if(v[x][i].first==prev)
            continue;
        pair<ll,bool> p=dfs(v[x][i].first,x);
        if(p.second)
        {
            brojac+=(p.first+v[x][i].second);
            cc=true;
        }
    }
    if(oznaceni[x])
        cc=true;
    return make_pair(brojac,cc);
}
using namespace std;
int main()
{
    int n,k,m;
    scanf("%d%d%d",&n,&k,&m);
    int pp=-1;
    vector<pair<int,ll> > vec;
    v.insert(v.begin(),n+1,vec);
    for(int i=0;i<k;i++)
    {
        int a;
        scanf("%d",&a);
        a--;
        pp=a;
        oznaceni[a]=true;
    }
    priority_queue<node> pq;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        a--;
        b--;
        node g;
        g.a=a;
        g.b=b;
        g.val=(ll)c;
        pq.push(g);
    }
    while(!pq.empty())
    {
        node g=pq.top();
        pq.pop();
        int a=g.a;
        int b=g.b;
        int aa=a;
        int bb=b;
        a=dsu(a);
        b=dsu(b);
        if(a==b)
            continue;
        else
        {
            v[aa].push_back(make_pair(bb,g.val));
            v[bb].push_back(make_pair(aa,g.val));
            if(d[a]>d[b])
            {
                d[b]++;
                p[a]=b;
                dsu1(aa,b);
            }
            else
            {
                d[a]++;
                p[b]=a;
                dsu1(bb,a);
            }
        }
    }
    cout<<dfs(pp,-1).first<<endl;
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'std::pair<long long int, bool> dfs(int, int)':
cities.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                  ^
cities.cpp: In function 'int main()':
cities.cpp:59:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&k,&m);
                             ^
cities.cpp:66:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a);
                       ^
cities.cpp:75:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
                                 ^

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