oj.uz

답안 #1074486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074486 2024-08-25T10:46:02 Z Malix 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 193 ms 53456 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(a,b,c) for(int a=b;a<c;a++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;
typedef pair<int,int> pi;
typedef vector<pi> pii;

vii a;
int k=0;
int p=log2(1000000000);
int arr[150000][35][2];
int brr[150000][35][2];

int solve(int x,int y){
  int t=0;
  while(y){
    int z=LSOne(y);
    pi tmp;
    tmp.F=arr[x][(int)log2(z)+1][t];
    tmp.S=brr[x][(int)log2(z)+1][t];
    x=tmp.F;
    if(tmp.S==a[x][0])t=1;
    else t=0;
    y-=z;
  }
  return x;
}

void count_routes(int n, int m, int P, int R[][2], int Q, int G[])
{
  a.resize(n);
  REP(i,0,m){
    int x=R[i][0];
    int y=R[i][1];
    a[x].PB(y);
    a[y].PB(x);
  }
  REP(i,0,n){
    arr[i][1][0]=a[i][0];
    brr[i][1][0]=i;
    if(a[i].size()==1){
      arr[i][1][1]=a[i][0];
      brr[i][1][1]=i;
    }
    else{
      arr[i][1][1]=a[i][1];
      brr[i][1][1]=i;
    } 
  }
  //1 - came from larger
  REP(j,2,p+1)REP(i,0,n){
    pi x,y;
    x.F=arr[i][j-1][0];
    x.S=brr[i][j-1][0];
    y.F=arr[i][j-1][1];
    y.S=brr[i][j-1][1];
    if(x.S==a[x.F][0]){
      arr[i][j][0]=arr[x.F][j-1][1];
      brr[i][j][0]=brr[x.F][j-1][1];
    }
    else{
      arr[i][j][0]=arr[x.F][j-1][0];
      brr[i][j][0]=brr[x.F][j-1][0];
    } 
    if(y.S==a[y.F][0]){
      arr[i][j][1]=arr[y.F][j-1][1];
      brr[i][j][1]=brr[y.F][j-1][1];
    }
    else{
      arr[i][j][1]=arr[y.F][j-1][0];
      brr[i][j][1]=brr[y.F][j-1][0];
    } 
  }
  int ans=0;
  REP(i,0,n)if(solve(i,G[0])==P)ans++;
  answer(ans);
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 22 ms 14220 KB Output is correct
12 Correct 43 ms 23640 KB Output is correct
13 Incorrect 193 ms 53456 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 22 ms 14220 KB Output is correct
12 Correct 43 ms 23640 KB Output is correct
13 Incorrect 193 ms 53456 KB Output isn't correct
14 Halted 0 ms 0 KB -