제출 #302688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302688		kevlee	Simurgh (IOI17_simurgh)	C++17	51 / 100	304 ms	7032 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
vi ans;
int m;
vp edges[505];
vi nodes[505];
int group[505];
bool used[505];
int asked[50005];
int f(int x) {
  return x == group[x] ? x : group[x] = f(group[x]);
}
vi find_roads(int n, vi u, vi v) {
  m = u.size();
  FOR(i, 0, m-1) {
    edges[u[i]].emplace_back(v[i], i);
    edges[v[i]].emplace_back(u[i], i);
  }
  FOR(i, 0, n-1) {
    int sz = edges[i].size();
    if (sz == 1) {
      ans.pb(edges[i][0].se);
      continue;
    }
    FOR(j, 0, n-1) group[j] = j;
    vi query;
    FOR(j, 0, m-1) {
      if (u[j] == i || v[j] == i) continue;
      int x = f(u[j]);
      int y = f(v[j]);
      if (x != y) {
        query.pb(j);
        group[x] = y;
      }
    }
    FOR(j, 0, n-1) nodes[j].clear();
    FOR(j, 0, edges[i].size() - 1) {
      nodes[f(edges[i][j].fi)].pb(edges[i][j].fi);
    }
    FOR(k, 0, n-1) {
      //cout << i <<"  "<<k << "  " << nodes[k].size() << endl; 
      if (nodes[k].size() == 0 || k == i) continue;
      vp res;
      vi ask = query;
      FOR(j, 0, n-1) used[j] = false;
      used[k] = used[i] = true;
      vi candidate;
      FOR(j, 0, edges[i].size() - 1) {
        int x = f(edges[i][j].fi);
        if (!used[x]) {
          used[x] = true;
          ask.pb(edges[i][j].se);
        } else if (x == k) {
          candidate.pb(edges[i][j].se);
        }
      }
      bool fir = true;
      for (auto it: candidate) {
        if (asked[it]) {
          if (asked[it] == 2 && fir) {
            fir = false;
            goto there;
          }
          continue;
        }
        there:;
        ask.pb(it);
        asked[it] = 1;
        //for (auto q: ask) cout << q <<' ';
        //cout << endl;
        int cnt = count_common_roads(ask);
        res.pb({cnt, it});
        ask.pop_back();
      }
    
      sort(res.rbegin(), res.rend());
      for (auto p: res) {
        if (p.fi != res[0].fi) {
          break;
        }
        ans.pb(p.se);
        asked[p.se] = 2;
      }
    }
  }
  sort(all(ans));
  auto iter = unique(all(ans));
  ans.resize(distance(ans.begin(), iter));
  //cout << ans.size() << endl;
  //for (auto it: ans) cout << it << ' ' ;
  //cout << endl;
  return ans;
}

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

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
      |                                          ^
simurgh.cpp:59:5: note: in expansion of macro 'FOR'
   59 |     FOR(j, 0, edges[i].size() - 1) {
      |     ^~~
simurgh.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
      |                                          ^
simurgh.cpp:70:7: note: in expansion of macro 'FOR'
   70 |       FOR(j, 0, edges[i].size() - 1) {
      |       ^~~

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