제출 #137973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137973		toonewbie	Simurgh (IOI17_simurgh)	C++17	30 / 100	380 ms	3704 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 55;
const int _ = 1;
int g[N][N], gud[N * N];
vector <int> cur;

int n;
int used[N];
void init(int v) {
  used[v] = 1;
  for (int i = 0; i < n; i++) {
    if (used[i] == 0 && g[v][i] > -1) {
      cur.push_back(g[v][i]);
      init(i);
    }
  }
}
void dfs(int v) {
  used[v] = 1;
  for (int i = 0; i < n; i++) {
    if (used[i] == 0 && g[v][i] > -1 && gud[g[v][i]] == 1) {
      dfs(i);
    }
  }
}
 
int check() {
  memset(used, 0, sizeof(used));
  memset(gud, 0, sizeof(gud));
  for (int i : cur) gud[i] = 1;
  dfs(0);
  for (int i = 0; i < n; i++) {
    if (used[i] == 0) return 0;
  }
  return 1;
}
 
vector <int> find_roads(int n, vector <int> u, vector <int> v) {
  ::n = n;
  int m = u.size();
  memset(g, -1, sizeof(g));
  for (int i = 0; i < m; i++) {
    g[u[i]][v[i]] = g[v[i]][u[i]] = i;
  }
  init(0);
  while(3^_^3) {
    int now = count_common_roads(cur);
    if (now == n - 1) return cur;
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < m; j++) {
        if (cur[i] != j) {
          int old = cur[i];
          cur[i] = j;
          if (check() == 1) {
            int noww = count_common_roads(cur);
            if (noww > now) {
              now = noww;
            } else cur[i] = old;
          } else cur[i] = old;
        }
      }
    }
  }
}

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