結果

問題 No.19 ステージの選択
ユーザー imgry22
提出日時 2014-12-23 21:19:35
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,245 bytes
コンパイル時間 1,354 ms
コンパイル使用メモリ 162,540 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 04:13:41
合計ジャッジ時間 2,388 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 3
権限があれば一括ダウンロードができます

ソースコード

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; !used[s[next]]; next=s[next]){
      uf.unite(i, next);
      used[next] = true;
      minup(mn, l[next]);
    }

    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