제출 #236847

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
236847	2020-06-03 15:01:41	kostia244	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	69 / 100	5064 ms	39744 KiB

garden

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 300500, mlg = 30;
int up[maxn][mlg], cnt[maxn];
void count_routes(int n, int m, int P, int R[][2], int Q, int G[]) {
  memset(cnt, 0, sizeof cnt);
  memset(up, -1, sizeof up);
  for(int i = 0; i < m; i++) {
    int f = R[i][0], t = R[i][1];
    //cout << f << " " << t << " " << i << '\n';
    if(cnt[f] < 2) up[2*f + cnt[f]][0] = 2*t + (cnt[t]==0);//, cout << 2*f + cnt[f] << " -- " << 2*t + (cnt[t]==0) << '\n';
    if(cnt[t] < 2) up[2*t + cnt[t]][0] = 2*f + (cnt[f]==0);//, cout << 2*t + cnt[t] << " -- " << 2*f + (cnt[f]==0) << '\n';
    cnt[f]++, cnt[t]++;
  }
  for(int i = 0; i < 2*n; i++) if(up[i][0] < 0) up[i][0] = up[i^1][0];
  for(int i = 1; i < mlg; i++)
    for(int j = 0; j < 2*n; j++)
      up[j][i] = up[up[j][i-1]][i-1];
  //for(int i = 0; i < 2*n; i++) cout << i << " = " << up[i][0] << "\n";
  for(int I = 0; I < Q; I++) {
    //cout << P << " " << G[I] << '\n';
    int ans = 0;
    for(int i = 0; i < 2*n; i+=2) cnt[i] = i;
    for(int i = 0; i < mlg; i++) {
      if(!((G[I]>>i)&1)) continue;
      for(int j = 0; j < 2*n; j+=2) {
        cnt[j] = up[cnt[j]][i];
      }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31