제출 #72816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72816		funcsr	Simurgh (IOI17_simurgh)	C++17	51 / 100	192 ms	6568 KiB

simurgh

#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) {
        int t = R[i][0];
        assert(ret[x][t] != 0);
        ret[x][t] = ret[t][x] = 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);
          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;
}

컴파일 시 표준 에러 (stderr) 메시지

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:69:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(rdef.size()==N-1);
            ~~~~~~~~~~~^~~~~
simurgh.cpp:87: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:96:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           assert(r.size()==N-1);
                  ~~~~~~~~^~~~~
simurgh.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(r.size() == N-1);
          ~~~~~~~~~^~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30