답안 #780708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780708	2023-07-12T11:55:08 Z	vjudge1	Simurgh (IOI17_simurgh)	C++17	51 / 100	85 ms	5432 KB

simurgh

#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) {
  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;
}

int mat[nmax][nmax];
  vector<int> isgood;
  vector<int> checked;

void solvefori(int 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);
  }
  
  int startmn = sz(candr) - 1;
  copy(all(nv), back_inserter(candr));
  
  for(int i = 1; i <= flag; i++) {
    //cerr << "--\n";
    vector<int> rez;
    int mx = -1; 
    for(int j = 0; j < sz(atrs[i]); j++) {
      int u = atrs[i][j];
      candr[startmn + i] = u;
      if(checked[u] && isgood[u]) { mx = ask(candr); break; }
    }
    for(int j = 0; j < sz(atrs[i]); j++) {
      int u = atrs[i][j];
      candr[startmn + i] = u;
      if(!checked[u])
        rez.emplace_back(ask(candr));
      else
        rez.emplace_back(-1);
    }
    if(mx == -1)
      mx = *max_element(all(rez));
    for(int j = 0; j < sz(atrs[i]); j++) {
      checked[atrs[i][j]] = 1;
      if(rez[j] == mx)
        isgood[atrs[i][j]] = 1;
    }
  }
}

vector<int> S4(int n, vector<int> u, vector<int> v) {
  for(int i = 0; i < sz(u); i++) {
    mat[u[i]][v[i]] = i;
    mat[v[i]][u[i]] = i;
    
    g[u[i]].emplace_back(v[i], i);
    g[v[i]].emplace_back(u[i], i);
  }
  
  //cerr << "yura\n";
  solvefori(0);
  for(int j = 1; j < n; j++) checked[mat[j][0]] = 1;
  for(int i = 1; i < n; i++) {
    vector<int> crr;
    for(int j = 0; j < n; j++) {
      if(j == i) continue;
      crr.emplace_back(mat[i][j]);
    }
    int totaltf = ask(crr);
    for(int j = 0; j < i; j++)
      totaltf -= isgood[mat[i][j]];
    for(int smth = 0; smth < totaltf; smth++) {
      auto trywith = [&](int lim) {
        vector<int> ntwr;
        ntwr.emplace_back(mat[0][i]);
        int expected = isgood[mat[0][i]];
        for(int j = 1; j <= lim; j++) {
          if(j == i) continue;
          ntwr.emplace_back(mat[i][j]);
          if(checked[mat[i][j]]) expected += isgood[mat[i][j]];
        }
        for(int j = lim + 1; j < n; j++) {
          if(j == i) continue;
          ntwr.emplace_back(mat[0][j]);
          if(checked[mat[i][j]]) expected += isgood[mat[i][j]];
        }
        return ask(ntwr) - expected;
      };
      int lim = i - 1;
      
      for(int i = 9; i >= 0; i--) {
        if(lim + (1 << i) >= n) continue;
        if(trywith(lim + (1 << i)) <= 0) lim += (1 << i);
      }
      lim++;
      checked[mat[i][lim]] = 1;
      isgood[mat[i][lim]] = 1;
    }
    
    for(int j = 0; j < n; j++) {
      if(j == i) continue;
      checked[mat[i][j]] = 1;
    }
      
  }
  vector<int> lst;
  for(int i = 0; i < sz(isgood); i++)
    if(isgood[i])
      lst.emplace_back(i);
  return lst;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
  isgood.resize(sz(u));
  checked.resize(sz(u));
  occ.resize(n);
  if(n > 240)
   return S4(n, u, v);
  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++) {
    solvefori(i);
  }
  
  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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	0 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	0 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	0 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	0 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct
14	Correct	1 ms	340 KB	correct
15	Correct	1 ms	340 KB	correct
16	Correct	1 ms	340 KB	correct
17	Correct	1 ms	340 KB	correct
18	Correct	1 ms	340 KB	correct
19	Correct	1 ms	340 KB	correct
20	Correct	1 ms	340 KB	correct
21	Correct	1 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	0 ms	212 KB	correct
26	Correct	1 ms	340 KB	correct
27	Correct	1 ms	340 KB	correct
28	Correct	1 ms	340 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
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	0 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	0 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct
14	Correct	1 ms	340 KB	correct
15	Correct	1 ms	340 KB	correct
16	Correct	1 ms	340 KB	correct
17	Correct	1 ms	340 KB	correct
18	Correct	1 ms	340 KB	correct
19	Correct	1 ms	340 KB	correct
20	Correct	1 ms	340 KB	correct
21	Correct	1 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	0 ms	212 KB	correct
26	Correct	1 ms	340 KB	correct
27	Correct	1 ms	340 KB	correct
28	Correct	1 ms	340 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	Correct	85 ms	1492 KB	correct
35	Correct	78 ms	1556 KB	correct
36	Correct	53 ms	1236 KB	correct
37	Correct	6 ms	340 KB	correct
38	Correct	77 ms	1492 KB	correct
39	Correct	66 ms	1364 KB	correct
40	Correct	53 ms	1348 KB	correct
41	Correct	77 ms	1560 KB	correct
42	Correct	85 ms	1548 KB	correct
43	Correct	44 ms	1108 KB	correct
44	Correct	36 ms	852 KB	correct
45	Correct	41 ms	960 KB	correct
46	Correct	31 ms	836 KB	correct
47	Correct	15 ms	468 KB	correct
48	Correct	2 ms	340 KB	correct
49	Correct	5 ms	340 KB	correct
50	Correct	15 ms	580 KB	correct
51	Correct	41 ms	956 KB	correct
52	Correct	35 ms	868 KB	correct
53	Correct	32 ms	836 KB	correct
54	Correct	43 ms	1156 KB	correct
55	Correct	46 ms	852 KB	correct
56	Correct	40 ms	852 KB	correct
57	Correct	40 ms	852 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	0 ms	212 KB	correct
3	Incorrect	43 ms	5432 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	0 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	0 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct
14	Correct	1 ms	340 KB	correct
15	Correct	1 ms	340 KB	correct
16	Correct	1 ms	340 KB	correct
17	Correct	1 ms	340 KB	correct
18	Correct	1 ms	340 KB	correct
19	Correct	1 ms	340 KB	correct
20	Correct	1 ms	340 KB	correct
21	Correct	1 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	0 ms	212 KB	correct
26	Correct	1 ms	340 KB	correct
27	Correct	1 ms	340 KB	correct
28	Correct	1 ms	340 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	Correct	85 ms	1492 KB	correct
35	Correct	78 ms	1556 KB	correct
36	Correct	53 ms	1236 KB	correct
37	Correct	6 ms	340 KB	correct
38	Correct	77 ms	1492 KB	correct
39	Correct	66 ms	1364 KB	correct
40	Correct	53 ms	1348 KB	correct
41	Correct	77 ms	1560 KB	correct
42	Correct	85 ms	1548 KB	correct
43	Correct	44 ms	1108 KB	correct
44	Correct	36 ms	852 KB	correct
45	Correct	41 ms	960 KB	correct
46	Correct	31 ms	836 KB	correct
47	Correct	15 ms	468 KB	correct
48	Correct	2 ms	340 KB	correct
49	Correct	5 ms	340 KB	correct
50	Correct	15 ms	580 KB	correct
51	Correct	41 ms	956 KB	correct
52	Correct	35 ms	868 KB	correct
53	Correct	32 ms	836 KB	correct
54	Correct	43 ms	1156 KB	correct
55	Correct	46 ms	852 KB	correct
56	Correct	40 ms	852 KB	correct
57	Correct	40 ms	852 KB	correct
58	Correct	0 ms	212 KB	correct
59	Correct	0 ms	212 KB	correct
60	Incorrect	43 ms	5432 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #780708

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0