oj.uz

답안 #928647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
928647 2024-02-17T00:24:42 Z OAleksa 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 2 ms 10840 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 150069;
const int K = 30;
int up[2 * N][K], vis[N], n, nxt[2 * N], deg[2 * N];
vector<int> t[N];
void dfs(int v) {
   vis[v] = 1;
   if (t[t[v][0]][0] == v && (int)t[t[v][0]].size() > 1)
      nxt[v] = n + t[v][0], deg[n + t[v][0]]++;
   else
      nxt[v] = t[v][0], deg[t[v][0]]++;
   if (t[v].size() > 1) {
      if (t[t[v][1]][0] == v && (int)t[t[v][1]].size() > 1)
         nxt[n + v] = n + t[v][1], deg[n + t[v][1]]++;
      else
         nxt[n + v] = t[v][1], deg[t[v][1]]++;
   }
   for (auto u : t[v]) {
      if (!vis[u])
         dfs(u);
   }
}

void count_routes(int n1, int m, int p, int r[][2], int q, int k[])
{
   ++p;
   n = n1;
   for (int i = 0;i < m;i++) {
      r[i][0]++, r[i][1]++;
      t[r[i][0]].push_back(r[i][1]);
      t[r[i][1]].push_back(r[i][0]);
   }
   for (int i = 1;i <= n;i++) {
      if (!vis[i])
         dfs(i);
   }
   //graf ima 2 * N cvorova!
   for (int i = 1;i <= 2 * n;i++)
      up[i][0] = nxt[i];
   for (int i = 1;i < K;i++) {
      for (int j = 1;j <= n;j++) {
         up[i][j] = up[up[i][j - 1]][j - 1];
      }
   }
   for (int i = 0;i < q;i++) {
      int ans = 0;
      for (int j = 1;j <= n;j++) {
         int d = j;
         for (int l = 0;l < K;l++) {
            if (k[i] >> l & 1)
               d = up[d][l];
         }
         ans += (d == p || d == n + p);
      }
      answer(ans);
   }
}
/*
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2

5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
1 2

*/

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -