#1857 (C++11) No.19 ステージの選択

提出ソース

結果

問題	No.19 ステージの選択
ユーザー	LayCurse
提出日時	2014-11-07 10:03:09
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2 ms / 5,000 ms
コード長	6,192 bytes
コンパイル時間	1,473 ms
コンパイル使用メモリ	163,108 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-02 12:27:34
合計ジャッジ時間	2,175 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	1 ms 6,944 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	1 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	1 ms 6,944 KB
testcase_12	AC	1 ms 6,944 KB
testcase_13	AC	1 ms 6,940 KB
testcase_14	AC	1 ms 6,940 KB
testcase_15	AC	1 ms 6,940 KB
testcase_16	AC	1 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	1 ms 6,944 KB
testcase_20	AC	1 ms 6,940 KB
testcase_21	AC	1 ms 6,944 KB
testcase_22	AC	1 ms 6,944 KB
testcase_23	AC	1 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

void* setDirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){int i;*es=(int*)workMemory;*edge=(int**)((*es)+N);(*edge)[0]=(int*)((*edge)+N);rep(i,N)(*es)[i]=0;rep(i,M)(*es)[A[i]]++;REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];workMemory=(void*)((*edge)[N-1]+(*es)[N-1]);rep(i,N)(*es)[i]=0;rep(i,M)(*edge)[A[i]][(*es)[A[i]]++]=B[i];return workMemory;}
void* setUndirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){int i;*es=(int*)workMemory;*edge=(int**)((*es)+N);(*edge)[0]=(int*)((*edge)+N);rep(i,N)(*es)[i]=0;rep(i,M)(*es)[A[i]]++,(*es)[B[i]]++;REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];workMemory=(void*)((*edge)[N-1]+(*es)[N-1]);rep(i,N)(*es)[i]=0;rep(i,M)(*edge)[A[i]][(*es)[A[i]]++]=B[i],(*edge)[B[i]][(*es)[B[i]]++]=A[i];return workMemory;}
void* getReverseGraph(int N, int *es, int **edge, int **r_es, int ***r_edge, void *workMemory){int i,j,k;*r_es=(int*)workMemory;*r_edge=(int**)((*r_es)+N);(*r_edge)[0]=(int*)((*r_edge)+N);rep(i,N)(*r_es)[i] = 0;rep(i,N)rep(j,es[i])(*r_es)[edge[i][j]]++;REP(i,1,N)(*r_edge)[i]=(*r_edge)[i-1]+(*r_es)[i-1];workMemory=(void*)((*r_edge)[N-1]+(*r_es)[N-1]);rep(i,N)(*r_es)[i]=0;rep(i,N)rep(j,es[i])k=edge[i][j],(*r_edge)[k][(*r_es)[k]++]=i;return workMemory;}

void getDepthOfTreeDFS(int node, int bef, int *depth, int *es, int **edge){int i,k;rep(i,es[node]){k=edge[node][i];if(bef==k)continue;depth[k]=depth[node] + 1;getDepthOfTreeDFS(k, node, depth, es, edge);}}
void* getDepthOfTree(int N, int root, int *es, int **edge, int **depth, void *workMemory){*depth=(int*)workMemory;workMemory=(void*)((*depth)+N);(*depth)[root]=0;getDepthOfTreeDFS(root,-1,*depth,es,edge);return workMemory;}

template<class T> void doublingRMQBuild(T arr[], int n, int res[]){int i,k,h;rep(i,n)res[i]=i;for(k=1;;k++){h=(1<<(k-1));if(h>=n)break;rep(i,n){res[n*k+i]=res[n*(k-1)+i];if(i+h<n&&arr[res[n*k+i]]>arr[res[n*(k-1)+i+h]])res[n*k+i]=res[n*(k-1)+i+h];}}}
template<class T> void* doublingRMQBuild(T arr[], int n, int **res, void *workMemory){int i,k,h;*res=(int*)workMemory;rep(i,n)(*res)[i]=i;for(k=1;;k++){h=(1<<(k-1));if(h>=n)break;rep(i,n){(*res)[n*k+i]=(*res)[n*(k-1)+i];if(i+h<n&&arr[(*res)[n*k+i]]>arr[(*res)[n*(k-1)+i+h]])(*res)[n*k+i]=(*res)[n*(k-1)+i+h];}}return (void*)((*res)+n*k);}
template<class T> int doublingRMQQuery(T arr[], int n, int rmq[], int a, int b){int d,w=b-a+1,A,B;for(d=0;(1<<(d+1))<=w;d++);A=rmq[n*d+a];B=rmq[n*d+b-(1<<d)+1];return arr[A]>arr[B]?B:A;}
struct LCA{
  int *depth, *vs, *id, *rmq, N, *es, **edge;
  void dfs(int node, int bef, int dep, int *num){int i,k;id[node]=*num;vs[*num]=node;depth[(*num)++]=dep;rep(i,es[node]){k=edge[node][i];if(k==bef)continue;dfs(k,node,dep+1,num);vs[*num]=node;depth[(*num)++]=dep;}}
  void* init(int N_, int root, int *es_, int **edge_, void *workMemory){int m=0;N=N_;es=es_;edge=edge_;depth=(int*)workMemory;vs=depth+2*N-1;id=vs+2*N-1;dfs(root,-1,0,&m);return doublingRMQBuild(depth,2*N-1,&rmq,(void*)(id+N));}
  int get(int a, int b){return vs[doublingRMQQuery(depth, 2*N-1, rmq, min(id[a],id[b]), max(id[a],id[b]))];}
  int getDepth(int a, int b){return depth[doublingRMQQuery(depth,2*N-1,rmq,min(id[a],id[b]),max(id[a],id[b]))];}
};

int StronglyConnectedComponentsDFS(int *es, int **edge, int num[], int st, int mx){
  int i,j;
  num[st]=-2;
  rep(i,es[st]) {
    j=edge[st][i]; if(num[j]==-1) mx=StronglyConnectedComponentsDFS(es,edge,num,j,mx);
  }
  num[st]=mx; return mx+1;
}

int StronglyConnectedComponents(int N, int *es, int **edge, int res[], void *workMemory){
  int i, j, k, ret=0;
  int *r_es, **r_edge;
  int *st, st_size, *num, *nrv;

  workMemory = getReverseGraph(N, es, edge, &r_es, &r_edge, workMemory);
  st = (int*) workMemory; num = st+N; nrv = num + N;

  rep(i,N) res[i] = num[i] = -1;
  k = 0;
  rep(i,N) if(num[i]==-1) k = StronglyConnectedComponentsDFS(es,edge,num,i,k);
  rep(i,N) nrv[num[i]] = i;

  for(k=N-1;k>=0;k--) {
    i=nrv[k]; if(res[i]>=0)continue;
    res[i]=ret; st_size=0; st[st_size++]=i;
    while(st_size){
      i=st[--st_size];
      rep(j,r_es[i])
        if(res[r_edge[i][j]]==-1) res[r_edge[i][j]]=ret, st[st_size++]=r_edge[i][j];
    }
    ret++;
  }

  return ret;
}


int N;
int A[222], B[222], L[222];
int com[222], deg[222], mn[222];

int main(){
  int i, j, k, nn;
  int res;
  int *es, **edge;
  void *mem = malloc(10000000);

  reader(&N);
  rep(i,N) reader(L+i,A+i), A[i]--, B[i]=i;
  mem = setDirectEdge(N, N, A, B, &es, &edge, mem);

  nn = StronglyConnectedComponents(N, es, edge, com, mem);

  res = 0;
  rep(i,N) res += L[i];
  rep(i,N) if(com[A[i]] != com[B[i]]) deg[com[B[i]]]++;

  rep(i,nn) mn[i] = 10000;
  rep(i,N) mn[com[i]] = min(mn[com[i]], L[i]);

  rep(i,nn) if(!deg[i]) res += mn[i];

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

  return 0;
}

yukicoder

結果

テストケース

ソースコード