結果

問題 No.19 ステージの選択
ユーザー imgry22imgry22
提出日時 2014-12-23 21:25:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,262 bytes
コンパイル時間 1,424 ms
コンパイル使用メモリ 162,392 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-23 10:01:00
合計ジャッジ時間 2,282 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 1 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;

#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, n)    for(int (i)=1; (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, n)    for(int (i)=(n); (i)>=1; (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define mp            make_pair
#define pb            push_back
template<class T1, class T2> inline void minup(T1& m, T2 x){ if(m>x) m=static_cast<T2>(x); }
template<class T1, class T2> inline void maxup(T1& m, T2 x){ if(m<x) m=static_cast<T2>(x); }

#define INF 1000000000
#define MOD 1000000009
#define EPS 1E-9

struct UnionFind
{
  vi data;
  UnionFind(int size) : data(size, -1) {}
  bool unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x != y){
      if(data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  bool same(int x, int y){ return root(x) == root(y); }
  int root(int x){ return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x){ return -data[root(x)]; }
};

#define MAX_N 100

int n;
int l[MAX_N];
int s[MAX_N];
double res;
bool used[MAX_N];
int lev[MAX_N];

int main()
{
  cin >> n;
  rep(i, n) cin >> l[i] >> s[i];
  rep(i, n) s[i] -= 1;
  rep(i, n) res += l[i];

  UnionFind uf(n);
  rep(i, n) if(!used[i]){
    int next;
    int mn = INF;
    for(next=i; ; next=s[next]){
      uf.unite(i, next);
      used[next] = true;
      minup(mn, l[next]);
      if(used[s[next]]) break;
    }

    if(s[next] == i){
      lev[uf.root(i)] = mn;
      res += mn;
    }
    else{
      if(uf.same(i, s[next])){
        int st = next;
        mn = INF;
        for(next=s[next]; next!=st; next=s[next]){
          minup(mn, l[next]);
        }
        minup(mn, l[next]);
        lev[uf.root(i)] = mn;
        res += mn;
      }
      else{
        lev[uf.root(i)] = lev[uf.root(s[next])];
      }
    }
  }

  printf("%.1f\n", res / 2.0);

  return 0;
}
0