GCJ2016-1A

a.hs

import Data.Monoid
import Data.List
import Data.Array
import Data.PriorityQueue.FingerTree
import Control.Lens
import Control.Applicative
import Control.Monad
import Control.Monad.State
import Math.NumberTheory.Primes

{- 略 -}

main :: IO ()
main = interact $ ioProcess $ run solveA

solveA :: Proc String
solveA = do
  s <- line
  return $ flip execState "" $ forM_ s $ \c -> do
    st <- use id
    if null st
      then id .= [c]
      else if head st <= c
        then id .= c:st
        else id .= st ++ [c]

b.cpp

#include<iostream>
#include<queue>

int main(){
  int ti;
  std::cin >> ti;
  for(int txi = 1; txi <= ti; txi++){
    int n;
    std::cin >> n;
    std::vector<bool> ib(n*2-1,true);
    std::vector<std::vector<int> > iv(n*2-1,std::vector<int>(n));
    for(int i=0;i<n*2-1;i++){
      for(int j=0;j<n;j++){
        std::cin >> iv[i][j];
      }
    }
    std::vector<std::vector<int> > vs1,vs2;
    std::vector<int> ci;
    int idx = 0;
    for(int i=0;i<n;i++){
      bool b = false,con = false;
      int v1=-1,v2=-1;
      int m = 2501;
      for(int j=0;j<iv.size();j++){
        if(ib[j] && iv[j][i] <= m){
          if(iv[j][i] < m){
            m = iv[j][i];
            b = con = false;
          }
          if(!b){
            v1 = j;
            b = true;
          }else{
            v2 = j;
            con = true;
          }
        }
      }
      if(!con){
        vs1.push_back(iv[v1]);
        vs2.push_back(iv[v1]);
        ci = iv[v1];
        idx = i;
        ib[v1] = false;
      }else{
        vs1.push_back(iv[v1]);
        vs2.push_back(iv[v2]);
        ib[v1] = ib[v2] = false;
      }
    }
    std::cout << "Case #" << txi << ":";
    for(int i=0;i<n;i++){
      if(idx == i){
        std::cout << " " << vs1[i][idx];
      }else if(vs1[i][idx] == ci[i]){
        std::cout << " " << vs2[i][idx];
      }else{
        std::cout << " " << vs1[i][idx];
      }
    }
    std::cout << std::endl;
  } 
  return 0;
}

c.cpp

#include<iostream>
#include<queue>

int retrive(int x,int b,const std::vector<std::vector<int> > &g){
  int mx = 0;
  for(int i=0;i<g[x].size();i++){
    if(g[x][i]!=b){
      int c = retrive(g[x][i],-1,g);
      if(mx < c)mx = c;
    }
  }
  return mx+1;
}

int main(){
  int ti;
  std::cin >> ti;
  for(int txi = 1; txi <= ti; txi++){
    int n;
    std::cin >> n;
    std::vector<bool> b(n);
    std::vector<int> f(n);
    std::vector<std::vector<int> > g(n);
    for(int i=0;i<n;i++){
      std::cin >> f[i], f[i]--, b[i] = false;
      g[f[i]].push_back(i);
    }
    std::vector<std::vector<int> > cycles;
    int mc = 0;
    for(int i=0;i<n;i++){
      std::vector<int> br(n,0);
      std::vector<int> cs;
      if(b[i]==false){
        int j = i;
        int cnt = 0;
        while(br[j]==0 && b[j]!=true){
          br[j] = ++cnt;
          cs.push_back(j);
          j = f[j];
        }
        if(b[j]==true)continue;
        cs = std::vector<int>(cs.begin()+br[j]-1,cs.end());
        for(int i=0;i<cs.size();i++){
          b[cs[i]] = true;
        }
        if(cs.size()>=3){
          if(mc<=cs.size())mc = cs.size();
        }else cycles.push_back(cs);
      }
    }
    int mr = 0;
    for(int i=0;i<cycles.size();i++){
      int d1 = retrive(cycles[i][0],cycles[i][1],g);
      int d2 = retrive(cycles[i][1],cycles[i][0],g);
      mr += d1+d2;
    }
    std::cout << "Case #" << txi << ": " << (mc<mr?mr:mc);
    std::cout << std::endl;
  } 
  return 0;
}