oj.uz

Submission #780641

# Submission time Handle Problem Language Result Execution time Memory
780641 2023-07-12T11:15:18 Z vjudge1 Simurgh (IOI17_simurgh) C++17
30 / 100
 91 ms 3628 KB 
#include <bits/stdc++.h>
#include "simurgh.h"

#define all(x) (x).begin(),(x).end()
using namespace std;

//#define ask count_common_roads 

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 500;

vector<pii> g[nmax];
vector<int> occ;
vector<int> candr;
int flag;

int cnt = 0;
int ask(vector<int> r) {
  cnt++;
  if(cnt >= 3e4) {
    assert(false);
  }
  return count_common_roads(r);
}

void dfs(int x) {
  occ[x] = flag;
  for(auto [y, ptr] : g[x]) {
    if(occ[y] != 0) continue;
    //cerr << x << ' ' << y << '\t' << ptr << '\n';
    occ[y] = flag;
    candr.emplace_back(ptr);
    dfs(y);
  }
  return;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
  occ.resize(n);
  vector<int> isgood(sz(u), 0);
  for(int i = 0; i < sz(u); i++) {
    g[u[i]].emplace_back(v[i], i);
    g[v[i]].emplace_back(u[i], i);
  }
  
  for(int i = 0; i < n; i++) {
    fill(all(occ), 0);
    candr.clear();
    occ[i] = -1;
    vector<vector<int>> atrs;
    atrs.emplace_back();
    vector<int> nv;
    flag = 0;
    for(auto [x, ptr] : g[i]) {
      if(occ[x] == 0) {
        flag++;
        dfs(x);
        nv.emplace_back(ptr);
        atrs.emplace_back();
        atrs.back().emplace_back(ptr);
      }
      else
        atrs[occ[x]].emplace_back(ptr);
    }
    
    //cerr << i <<'\n';
    //for(auto x : candr) cerr << x << ' ';
    //cerr << '\n';
    //for(auto x : nv) cerr << x << ' ';
    //cerr << '\n';
    
    
    int startmn = sz(candr) - 1;
    copy(all(nv), back_inserter(candr));
    
    for(int i = 1; i <= flag; i++) {
      //cerr << "--\n";
      vector<int> rez;
      for(int j = 0; j < sz(atrs[i]); j++) {
        int u = atrs[i][j];
        candr[startmn + i] = u;
        rez.emplace_back(ask(candr));
      }
      int mx = *max_element(all(rez));
      for(int j = 0; j < sz(atrs[i]); j++) {
        if(rez[j] == mx)
          isgood[atrs[i][j]] = 1;
      }
      //cerr << "--\n";
    }
    //cerr << "=======\n";
  }
  
  vector<int> lst;
  for(int i = 0; i < sz(isgood); i++)
    if(isgood[i])
      lst.emplace_back(i);
  
  for(auto x : lst)
    cerr << x << ' ';
  cerr << '\n';
  
  return lst;
}



/**
      Anul asta se da centroid.
-- Surse oficiale
*/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 1 ms 288 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 1 ms 288 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 2 ms 340 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 3 ms 340 KB correct
17 Correct 2 ms 340 KB correct
18 Correct 1 ms 328 KB correct
19 Correct 3 ms 340 KB correct
20 Correct 2 ms 364 KB correct
21 Correct 2 ms 340 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 1 ms 340 KB correct
24 Correct 1 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 1 ms 340 KB correct
27 Correct 1 ms 340 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 340 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 1 ms 288 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 2 ms 340 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 3 ms 340 KB correct
17 Correct 2 ms 340 KB correct
18 Correct 1 ms 328 KB correct
19 Correct 3 ms 340 KB correct
20 Correct 2 ms 364 KB correct
21 Correct 2 ms 340 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 1 ms 340 KB correct
24 Correct 1 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 1 ms 340 KB correct
27 Correct 1 ms 340 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 340 KB correct
34 Runtime error 91 ms 2724 KB Execution killed with signal 6
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Incorrect 60 ms 3628 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 1 ms 288 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 2 ms 340 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 3 ms 340 KB correct
17 Correct 2 ms 340 KB correct
18 Correct 1 ms 328 KB correct
19 Correct 3 ms 340 KB correct
20 Correct 2 ms 364 KB correct
21 Correct 2 ms 340 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 1 ms 340 KB correct
24 Correct 1 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 1 ms 340 KB correct
27 Correct 1 ms 340 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 340 KB correct
34 Runtime error 91 ms 2724 KB Execution killed with signal 6
35 Halted 0 ms 0 KB -