Submission #68421

#	Time	Username	Problem	Language	Result	Execution time	Memory
68421		Just_Solve_The_Problem	Simurgh (IOI17_simurgh)	C++11	0 / 100	4 ms	360 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
//#include "grader.cpp"

#define pb push_back
#define sz(s) (int)s.size()

using namespace std;

int nn;
bool fl;

void go(int cur, vector < vector < int > > &gr, vector < int > &ask, vector  < int > &ans) {
  if (fl) return ;
  if (cur + 1 == nn) {
    for (int to : gr[cur]) {
      ask[cur - 1] = to;
      int cnt = count_common_roads(ask);
      if (cnt == nn - 1) {
        ans = ask;
        fl = 1;
        return ;
      }
    }
    return ;
  }
  for (int to : gr[cur]) {
    ask[cur - 1] = to;
    go(cur + 1, gr, ask, ans);
  }
}

vector<int> find_roads(int n1, vector<int> U, vector<int> V) {
  vector < vector < int > > gr;
  vector < int > ask, ans, u1, v1;
  int m = U.size();
  nn = n1;
  ask.resize(nn - 1);
  ans.resize(nn - 1);
  gr.resize(nn);
  u1 = U;
  v1 = V;
  for (int i = 0; i < m; i++) {
    if (u1[i] > v1[i]) swap(u1[i], v1[i]);
    gr[v1[i]].pb(i);
  }
  go(1, gr, ask, ans);
  return ans;
}
/*
7 21
0 1
0 2
0 3
0 4
0 5
0 6
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
0 6 11 15 18 20
*/

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