Yandex.Algorithm 2015 Round 2.2 C問題 - Equality and Roads

Source

Yandex.Algorithm 2015
Yandex.Algorithm 2015 Round 2.2
問題文

問題概要

$N$ 個の街と $M$ 個の道がある.道は双方向に通れる.
$2$ つの民族がいて,それぞれの道はどちらかの民族の所有物である.
クエリが $Q$ 個与えられるので,それに答える問題.
$k$ 番目のクエリでは,整数 $A_k$ が与えられるので,民族 $1$ が所有する道を $A_k$ 個,民族 $2$ が所有する道を $N-A_k-1$ 個用いて(これらを共有化して,共有化された道のみを用いて)全ての街の間を行き来できるようにできるかどうかを判定する.

解法

民族 $1$ の道をコスト $1$ として,民族 $2$ の道のコストを $0$ としたときに,コスト $A_k$ の全域木は作れるかどうか判定するという問題になる.
まず,全域木がそもそも作れない場合は,全て答えは否.
全域木が作れるなら,クラスカルなどで,コストの小さい枝を優先的に使った場合(最小全域木)のコストと,コストの大きい枝を優先的に使った場合(最大全域木)のコストを計算して,$A_k$ がその間にあれば可能と判定すれば良い.

C++によるスパゲッティなソースコード

#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)

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);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}

void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

template<class T1, class T2, class T3> void sort(int N, T1 a[], T2 b[], T3 c[], void *mem){int i;pair<T1,pair<T2,T3> > *r=(pair<T1,pair<T2,T3> >*)mem;rep(i,N)r[i].first=a[i],r[i].second.first=b[i],r[i].second.second=c[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second.first,c[i]=r[i].second.second;}

char memarr[37000000]; void *mem = memarr;
#define MD 1000000007

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

int N, M, Q;
int A[222222], B[222222], C[222222];
int ind[111111];

int main(){
  int i, j, k;
  int cost1 = 0, cost2 = 0, con = 0;

  reader(&N,&M,&Q);
  rep(i,M) reader(A+i,B+i,C+i), A[i]--, B[i]--;
  sort(M, C, A, B, mem);

  unionInit(ind, N);
  rep(i,M){
    if(unionConnect(ind,A[i],B[i])){
      cost1 += C[i];
      con++;
    }
  }
  if(con != N-1){
    rep(i,Q) writerLn("NO");
    return 0;
  }

  unionInit(ind, N);
  for(i=M-1;i>=0;i--){
    if(unionConnect(ind,A[i],B[i])){
      cost2 += 1-C[i];
    }
  }

  while(Q--){
    reader(&i);
    if(i < cost2){ writerLn("NO"); continue; }
    if(N-1-i < cost1){ writerLn("NO"); continue; }
    writerLn("YES");
  }

  return 0;
}

Current time: 2017年11月19日12時15分15秒
Last modified: 2015年09月09日05時39分50秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2015 Yandex_Algorithm_2015_Round22
トップページに戻る

Logged in as: unknown user (not login)

ログイン: