oj.uz

답안 #72814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72814 2018-08-27T02:59:25 Z funcsr Simurgh (IOI17_simurgh) C++17
0 / 100
 3 ms 824 KB 
#include "simurgh.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cassert>
using namespace std;
#define rep(i,n)for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
typedef pair<int, int> P;

vector<int> R[500];
struct UF {
  int U[500];
  int find(int x){
    if(U[x]==x)return x;
    return U[x]=find(U[x]);
  }
  void unite(int x, int y) {
    x=find(x), y=find(y);
    if(x==y)return;
    U[x]=y;
  }
  bool same(int x, int y) { return find(x)==find(y);}
};


int M;
bool G[500][500];
int ID[500][500];
int ret[500][500];

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
  M = U.size();
  rep(i, M) G[U[i]][V[i]] = G[V[i]][U[i]] = true;
  rep(i, M) ID[U[i]][V[i]] = ID[V[i]][U[i]] = i;
  rep(i, N) rep(j, N) ret[i][j] = -1;

  UF uf;
  rep(x, N) {
    rep(i, N) uf.U[i] = i, R[i].clear();
    vector<int> cand;
    vector<int> def;
    rep(i, M) {
      if (V[i] == x) swap(U[i], V[i]);

      if (U[i] == x) cand.pb(V[i]);
      else {
        if (!uf.same(U[i], V[i])) {
          uf.unite(U[i], V[i]);
          def.pb(i);
        }
      }
    }
    //cout<<"x="<<x<<": def.size()="<<def.size()<<"\n";
    //cout<<"cand={";for (int  t:cand)cout<<t<<",";cout<<"}\n";

    for (int t : cand) if (ret[x][t] != -1) R[uf.find(t)].pb(t);
    for (int t : cand) if (ret[x][t] == -1) R[uf.find(t)].pb(t);

    vector<int> rdef(def);
    rep(i, N) if (!R[i].empty()) rdef.pb(ID[x][R[i][0]]);
    assert(rdef.size()==N-1);
    int cr = count_common_roads(rdef);
    //cout<<"cr="<<cr<<"\n";

    rep(i, N) if (!R[i].empty()) {
      if (R[i].size() == 1) continue;
      vector<int> r(def);
      rep(other, N) if (i!=other &&!R[other].empty()) r.pb(ID[x][R[other][0]]);
      r.pb(-1);
      int moto = R[i][0];
      int max_r = cr;
      vector<P> ps;
      ps.pb(P(moto, cr));
      for (int j=1; j<R[i].size(); j++) {
        int t = R[i][j];
        if (ret[x][t] != -1) {
          assert(ret[x][moto] != -1);
          max_r = max(max_r, cr-ret[x][moto]+ret[x][t]);
        }
        else {
          r.pop_back();
          r.pb(ID[x][t]);
          assert(r.size()==N-1);
          int res = count_common_roads(r);
          //cout<<"t="<<t<<": res="<<res<<"\n";
          max_r = max(max_r, res);
          ps.pb(P(t, res));
        }
      }
      for (P p : ps) {
        int t = p._1, c = p._2;
        if (c == max_r) {
          //cout<<x<<"<->"<<t<<": yes\n";
          // 1
          ret[x][t] = ret[t][x] = 1;
        }
        else {
          // 0
          ret[x][t] = ret[t][x] = 0;
        }
      }
    }
  }

  vector<int> r;
  rep(i, N) rep(j, i) if (ret[i][j]==1) r.pb(ID[i][j]);
  assert(r.size() == N-1);
  assert(count_common_roads(r) == N-1);
  return r;
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from simurgh.cpp:7:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(rdef.size()==N-1);
            ~~~~~~~~~~~^~~~~
simurgh.cpp:81:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j=1; j<R[i].size(); j++) {
                     ~^~~~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from simurgh.cpp:7:
simurgh.cpp:90:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           assert(r.size()==N-1);
                  ~~~~~~~~^~~~~
simurgh.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(r.size() == N-1);
          ~~~~~~~~~^~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 520 KB correct
4 Correct 2 ms 520 KB correct
5 Correct 3 ms 548 KB correct
6 Correct 3 ms 572 KB correct
7 Runtime error 3 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 520 KB correct
4 Correct 2 ms 520 KB correct
5 Correct 3 ms 548 KB correct
6 Correct 3 ms 572 KB correct
7 Runtime error 3 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 520 KB correct
4 Correct 2 ms 520 KB correct
5 Correct 3 ms 548 KB correct
6 Correct 3 ms 572 KB correct
7 Runtime error 3 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 520 KB correct
4 Correct 2 ms 520 KB correct
5 Correct 3 ms 548 KB correct
6 Correct 3 ms 572 KB correct
7 Runtime error 3 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -