oj.uz

Submission #1074486

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -