Hatena::Grouptopcoder

blu_rayの日記

2011-08-24

Codeforces Beta Round #83

| 20:14

oxx--

A. Palindromic Times / Accepted

結構時間かかった。submitまで27分で、決め打ちでやったほうが早かったのか..?

B. Datatypes / TLE

submitは1時間後で、システムテストで落ちてる。

N=10^6で、O(N)で済むところをO(N^2)にしてて見積もってなかったのが原因。

もったいない。

C. Dorm Water Supply / WA

入次数が0の頂点から出次数が0の頂点までDFSするというか辿るだけだったのに、

本番中は入次数0から始めないで適当に端からDFSしてたのが原因だった。

これももったいない。

struct Result {
  int tank, tap, diameter;
  Result():tank(0),tap(0),diameter(0){}
  Result(int a, int b, int c):tank(a),tap(b),diameter(c){}
  bool operator<(const Result& a) const {return tank < a.tank;}
};

int n, p, es[1002][1002], a, b, res_size;
bool used[1002];
Result result[1002];

void dfs(int from, int cur, int meter) {
  if (used[cur]) return;
  used[cur] = true;
  rep(i,n) if (es[cur][i] > 0) {
    dfs(from, i, min(meter, es[cur][i])); return;
  }
  if (from != cur) {
    result[res_size] = Result(from+1, cur+1, meter);
    res_size++;  
  }
}

int main(int argc, char* argv[]) {
  memset(es, -1, sizeof es);
  set<int> taps;
  cin>>n>>p;
  rep(i,p) {
    cin>>a>>b;
    a--; b--;
    taps.insert(b);
    cin>>es[a][b];
  }
  fill(used, used + n, false);
  rep(i,n) {
    if (!used[i] && !taps.count(i)) dfs(i, i, 1<<28);
  }
  if (res_size) {
    sort(result, result+res_size);
    printf("%d\n", res_size);
    rep(i,res_size)
      printf("%d %d %d\n", result[i].tank, result[i].tap, result[i].diameter);
  } else {
    puts("0");
  }
  return 0;
}

D. BasketBall Team

英語は読めたけど、Sample inputの2と3を見て混乱した。

E. Arrangement

未読

rate := 1366 -> 1336

そろそろ減り幅が少なくなってきた.

上で冷静に書いてて、ありえない勘違いが多すぎる気がする