oj.uz

답안 #347997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347997 2021-01-14T02:50:55 Z milleniumEeee 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
69 / 100
 5000 ms 69340 KB 
/*
ребра как вершины
*/
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define szof(s) (int)s.size()
using namespace std;
 
const int MAXN = 150005;
int n, m, q, p;
vector <pii> edges;
vector <pii> g[MAXN];
map <pii, int> mp;
vector <int> eg[MAXN * 2]; // edge graph
pii from_to[MAXN * 2];
int table[31][MAXN * 2];
 
int get(int v, int k) {
  int cur = v;
  for (int i = 30; i >= 0; i--) {
    if (k & (1 << i)) {
      cur = table[i][cur];
    }
  }
  return cur;
}
 
int solve(int k) {
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int ind = get(g[i][0].sc, k - 1);
    if (from_to[ind].sc == p) {
      ans++;
    }
  }
  return ans;
}

pii para(int pos) {
  int x = from_to[pos].fr, y = from_to[pos].sc;
  pii res = {min(x, y), max(x, y)};
  return res;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  n = N;
  m = M;
  q = Q;
  p = P;
  for (int i = 0; i < m; i++) {
    int x = R[i][0];
    int y = R[i][1];
    edges.pb({x, y});
    if (szof(g[x]) < 2) {
      g[x].pb({y, i});
    }
    if (szof(g[y]) < 2) {
      g[y].pb({x, i});
    }
  }
  int cnt = 0;
  for (int v = 0; v < n; v++) {
    for (auto &edge : g[v]) {
      int to = edge.fr, ind = edge.sc;
      mp[{v, to}] = cnt++;
      from_to[cnt - 1] = {v, to};
      edge.sc = cnt - 1;
    }
  }
  int sz = 0;
  
  for (int v = 0; v < n; v++) {
    for (auto edge : g[v]) {
      int to = edge.fr, ind = edge.sc;
      sz++;
      if (szof(g[to]) == 1) {
        eg[ind].pb(mp[{to, v}]);
        continue;
      }
      pii cur = para(ind);
      pii mn1 = para(mp[{to, g[to][0].fr}]);
      pii mn2 = para(mp[{to, g[to][1].fr}]);  
      if (cur != mn1) {
        eg[ind].pb(mp[{to, g[to][0].fr}]);
      } else {
        eg[ind].pb(mp[{to, g[to][1].fr}]);
      }
    }
  }
  for (int pw = 0; pw < 30; pw++) {
    if (pw == 0) {
      for (int v = 0; v < sz; v++) {
        table[pw][v] = eg[v][0];
      }
    } else {
      for (int v = 0; v < sz; v++) {
        table[pw][v] = table[pw - 1][table[pw - 1][v]];
      }
    }
  }
  for (int i = 0; i < q; i++) {
    answer(solve(G[i]));
  }
}


//static int N, M, P, Q;
//static int R[MAXN][2];
//static int G[MAXN];

//signed main() {
  //cin >> N >> M >> P;
  //for (int i = 0; i < M; i++) {
    //cin >> R[i][0] >> R[i][1];
  //}
  //cin >> Q;
  //for (int i = 0; i < Q; i++) {
    //cin >> G[i];
  //}
  //count_routes(N, M, P, R, Q, G);
//}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:71:25: warning: unused variable 'ind' [-Wunused-variable]
   71 |       int to = edge.fr, ind = edge.sc;
      |                         ^~~
garden.cpp:89:11: warning: variable 'mn2' set but not used [-Wunused-but-set-variable]
   89 |       pii mn2 = para(mp[{to, g[to][1].fr}]);
      |           ^~~

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11500 KB Output is correct
2 Correct 9 ms 11500 KB Output is correct
3 Correct 10 ms 11628 KB Output is correct
4 Correct 8 ms 11116 KB Output is correct
5 Correct 8 ms 11116 KB Output is correct
6 Correct 10 ms 11628 KB Output is correct
7 Correct 8 ms 11116 KB Output is correct
8 Correct 9 ms 11500 KB Output is correct
9 Correct 11 ms 11756 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11500 KB Output is correct
2 Correct 9 ms 11500 KB Output is correct
3 Correct 10 ms 11628 KB Output is correct
4 Correct 8 ms 11116 KB Output is correct
5 Correct 8 ms 11116 KB Output is correct
6 Correct 10 ms 11628 KB Output is correct
7 Correct 8 ms 11116 KB Output is correct
8 Correct 9 ms 11500 KB Output is correct
9 Correct 11 ms 11756 KB Output is correct
10 Correct 8 ms 11116 KB Output is correct
11 Correct 46 ms 20456 KB Output is correct
12 Correct 106 ms 27748 KB Output is correct
13 Correct 173 ms 52448 KB Output is correct
14 Correct 431 ms 65116 KB Output is correct
15 Correct 435 ms 66652 KB Output is correct
16 Correct 338 ms 53952 KB Output is correct
17 Correct 302 ms 48988 KB Output is correct
18 Correct 106 ms 28260 KB Output is correct
19 Correct 431 ms 65064 KB Output is correct
20 Correct 439 ms 66804 KB Output is correct
21 Correct 342 ms 53980 KB Output is correct
22 Correct 281 ms 48860 KB Output is correct
23 Correct 466 ms 69340 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11500 KB Output is correct
2 Correct 9 ms 11500 KB Output is correct
3 Correct 10 ms 11628 KB Output is correct
4 Correct 8 ms 11116 KB Output is correct
5 Correct 8 ms 11116 KB Output is correct
6 Correct 10 ms 11628 KB Output is correct
7 Correct 8 ms 11116 KB Output is correct
8 Correct 9 ms 11500 KB Output is correct
9 Correct 11 ms 11756 KB Output is correct
10 Correct 8 ms 11116 KB Output is correct
11 Correct 46 ms 20456 KB Output is correct
12 Correct 106 ms 27748 KB Output is correct
13 Correct 173 ms 52448 KB Output is correct
14 Correct 431 ms 65116 KB Output is correct
15 Correct 435 ms 66652 KB Output is correct
16 Correct 338 ms 53952 KB Output is correct
17 Correct 302 ms 48988 KB Output is correct
18 Correct 106 ms 28260 KB Output is correct
19 Correct 431 ms 65064 KB Output is correct
20 Correct 439 ms 66804 KB Output is correct
21 Correct 342 ms 53980 KB Output is correct
22 Correct 281 ms 48860 KB Output is correct
23 Correct 466 ms 69340 KB Output is correct
24 Correct 18 ms 11244 KB Output is correct
25 Correct 4270 ms 20708 KB Output is correct
26 Execution timed out 5059 ms 28516 KB Time limit exceeded
27 Halted 0 ms 0 KB -