Submission #315233


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef queue<int> qi;


struct Edge{
  int u,v; ll cost;
  bool operator<(const Edge &a)const{
    return cost < a.cost;
  }
};

struct UnionFind{
  int par[100005];
  int rank[100005];
  UnionFind(){ init(); }
  void init(){
    rep(i,100005){
      par[i] = i;
      rank[0];
    }
  }
  int find(int x){
    if(x==par[x]) return x;
    return par[x] = find(par[x]);
  }
  int same(int x, int y){
    return find(x)==find(y);
  }
  void unite(int x, int y){
    x = find(x); y = find(y);
    if(x==y) return;
    if(rank[x] < rank[y]){
      par[x] = y;
    }else{
      par[y] = x;
      if(rank[x]==rank[y]) rank[x]++;
    }
  }
};

int N,M;
vector<Edge>es;

int main(){
  scanf("%d%d",&N,&M);
  rep(i,N){
    ll c;
    scanf("%lld", &c);
    es.PB((Edge){0,i+1,c});
  }
  rep(i,M){
    int a, b; ll r;
    scanf("%d%d%lld", &a,&b,&r);
    es.PB((Edge){a,b,r});
  }

  sort(es.begin(), es.end());

  UnionFind uf;
  ll res = 0;
  rep(i,es.size()){
    Edge e = es[i];
    if(!uf.same(e.u, e.v)){
      uf.unite(e.u, e.v);
      res += e.cost;
    }
  }

  printf("%lld\n", res);
  return 0;
}

Submission Info

Submission Time
Task C - 高橋君と国家
User raven38
Language C++ (G++ 4.6.4)
Score 100
Code Size 1975 Byte
Status
Exec Time 249 ms
Memory 9124 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:77:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:80:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:85:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt
Subtask1 10 / 10 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt
Subtask2 20 / 20 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt
Subtask3 30 / 30 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt
Subtask4 40 / 40 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt, subtask4-01.txt, subtask4-02.txt, subtask4-03.txt, subtask4-04.txt, subtask4-05.txt, subtask4-06.txt, subtask4-07.txt, subtask4-08.txt, subtask4-09.txt, subtask4-10.txt, subtask4-11.txt, subtask4-12.txt, subtask4-13.txt, subtask4-14.txt, subtask4-15.txt, subtask4-16.txt, subtask4-17.txt, subtask4-18.txt, subtask4-19.txt, subtask4-20.txt, subtask4-21.txt, subtask4-22.txt, subtask4-23.txt, subtask4-24.txt, subtask4-25.txt, subtask4-26.txt, subtask4-27.txt, subtask4-28.txt, subtask4-29.txt, subtask4-30.txt
Case Name Status Exec Time Memory
subtask0-sample-01.txt 27 ms 1292 KB
subtask0-sample-02.txt 27 ms 1296 KB
subtask0-sample-03.txt 26 ms 1300 KB
subtask1-01.txt 26 ms 1300 KB
subtask1-02.txt 25 ms 1300 KB
subtask1-03.txt 26 ms 1260 KB
subtask1-04.txt 27 ms 1296 KB
subtask1-05.txt 26 ms 1260 KB
subtask1-06.txt 25 ms 1296 KB
subtask1-07.txt 26 ms 1260 KB
subtask1-08.txt 26 ms 1272 KB
subtask1-09.txt 26 ms 1300 KB
subtask1-10.txt 26 ms 1384 KB
subtask1-11.txt 27 ms 1260 KB
subtask1-12.txt 25 ms 1236 KB
subtask1-13.txt 26 ms 1296 KB
subtask1-14.txt 25 ms 1296 KB
subtask1-15.txt 27 ms 1260 KB
subtask1-16.txt 26 ms 1300 KB
subtask1-17.txt 25 ms 1292 KB
subtask1-18.txt 26 ms 1296 KB
subtask1-19.txt 28 ms 1264 KB
subtask1-20.txt 25 ms 1296 KB
subtask1-21.txt 26 ms 1256 KB
subtask1-22.txt 26 ms 1388 KB
subtask1-23.txt 25 ms 1236 KB
subtask1-24.txt 27 ms 1264 KB
subtask1-25.txt 27 ms 1292 KB
subtask1-26.txt 27 ms 1264 KB
subtask1-27.txt 25 ms 1232 KB
subtask1-28.txt 27 ms 1256 KB
subtask1-29.txt 27 ms 1296 KB
subtask1-30.txt 27 ms 1260 KB
subtask2-01.txt 27 ms 1260 KB
subtask2-02.txt 26 ms 1292 KB
subtask2-03.txt 27 ms 1256 KB
subtask2-04.txt 27 ms 1256 KB
subtask2-05.txt 26 ms 1304 KB
subtask2-06.txt 26 ms 1304 KB
subtask2-07.txt 24 ms 1300 KB
subtask2-08.txt 26 ms 1260 KB
subtask2-09.txt 26 ms 1236 KB
subtask2-10.txt 26 ms 1260 KB
subtask2-11.txt 25 ms 1296 KB
subtask2-12.txt 26 ms 1308 KB
subtask2-13.txt 26 ms 1268 KB
subtask2-14.txt 29 ms 1268 KB
subtask2-15.txt 26 ms 1304 KB
subtask2-16.txt 25 ms 1304 KB
subtask2-17.txt 25 ms 1304 KB
subtask2-18.txt 26 ms 1304 KB
subtask2-19.txt 25 ms 1304 KB
subtask2-20.txt 24 ms 1260 KB
subtask2-21.txt 25 ms 1296 KB
subtask2-22.txt 26 ms 1268 KB
subtask2-23.txt 25 ms 1300 KB
subtask2-24.txt 26 ms 1304 KB
subtask2-25.txt 26 ms 1304 KB
subtask2-26.txt 26 ms 1268 KB
subtask2-27.txt 26 ms 1300 KB
subtask2-28.txt 28 ms 1256 KB
subtask2-29.txt 26 ms 1300 KB
subtask2-30.txt 27 ms 1260 KB
subtask3-01.txt 27 ms 1256 KB
subtask3-02.txt 27 ms 1308 KB
subtask3-03.txt 33 ms 1268 KB
subtask3-04.txt 29 ms 1260 KB
subtask3-05.txt 31 ms 1388 KB
subtask3-06.txt 30 ms 1264 KB
subtask3-07.txt 28 ms 1432 KB
subtask3-08.txt 28 ms 1396 KB
subtask3-09.txt 29 ms 1396 KB
subtask3-10.txt 28 ms 1396 KB
subtask3-11.txt 29 ms 1428 KB
subtask3-12.txt 28 ms 1428 KB
subtask3-13.txt 27 ms 1432 KB
subtask3-14.txt 30 ms 1524 KB
subtask3-15.txt 28 ms 1516 KB
subtask3-16.txt 31 ms 1512 KB
subtask3-17.txt 30 ms 1516 KB
subtask3-18.txt 31 ms 1516 KB
subtask3-19.txt 31 ms 1520 KB
subtask3-20.txt 31 ms 1520 KB
subtask3-21.txt 30 ms 1512 KB
subtask3-22.txt 30 ms 1520 KB
subtask3-23.txt 31 ms 1516 KB
subtask3-24.txt 30 ms 1516 KB
subtask3-25.txt 31 ms 1512 KB
subtask3-26.txt 31 ms 1512 KB
subtask3-27.txt 29 ms 1544 KB
subtask3-28.txt 29 ms 1512 KB
subtask3-29.txt 30 ms 1520 KB
subtask3-30.txt 30 ms 1520 KB
subtask4-01.txt 34 ms 1640 KB
subtask4-02.txt 38 ms 1772 KB
subtask4-03.txt 42 ms 1892 KB
subtask4-04.txt 101 ms 3424 KB
subtask4-05.txt 134 ms 5088 KB
subtask4-06.txt 183 ms 5592 KB
subtask4-07.txt 191 ms 5660 KB
subtask4-08.txt 132 ms 5088 KB
subtask4-09.txt 161 ms 5188 KB
subtask4-10.txt 236 ms 9116 KB
subtask4-11.txt 238 ms 9120 KB
subtask4-12.txt 247 ms 9116 KB
subtask4-13.txt 236 ms 9116 KB
subtask4-14.txt 239 ms 9116 KB
subtask4-15.txt 238 ms 9116 KB
subtask4-16.txt 243 ms 9124 KB
subtask4-17.txt 235 ms 9116 KB
subtask4-18.txt 247 ms 9116 KB
subtask4-19.txt 249 ms 9120 KB
subtask4-20.txt 241 ms 9116 KB
subtask4-21.txt 243 ms 9116 KB
subtask4-22.txt 236 ms 9116 KB
subtask4-23.txt 241 ms 9112 KB
subtask4-24.txt 240 ms 9120 KB
subtask4-25.txt 235 ms 9120 KB
subtask4-26.txt 238 ms 9108 KB
subtask4-27.txt 239 ms 9112 KB
subtask4-28.txt 237 ms 9116 KB
subtask4-29.txt 236 ms 9116 KB
subtask4-30.txt 235 ms 9116 KB