oj.uz

Submission #392459

# Submission time Handle Problem Language Result Execution time Memory
392459 2021-04-21T08:00:44 Z Hazem Tropical Garden (IOI11_garden) C++14
49 / 100
 4816 ms 262148 KB 
#include <bits/stdc++.h>
#include "gardenlib.h"
//#include "grader.h"
using namespace std;
 
#define S second
#define F first
#define LL long long 
 
const int N1 = 2e5+10;
const LL MOD = 1e9+7;
const LL LINF = 1e18;
const LL INF = 1e9;

map<pair<LL,int>,LL>nxt;
vector<pair<int,int>>adj[N1];

int get_after(int i,int k){

    int pre = INF;
    for(int j=30;j>=0;j--)
        if((1<<j)>k)continue;
        else {
            
            LL val = nxt[{i+pre*INF,j}];
            i = val%INF,pre = val/INF;
            k -= 1<<j;
        }
    return i;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{   

    int n = N;
    for(int i=0;i<M;i++){
        adj[R[i][0]].push_back({i,R[i][1]});
        adj[R[i][1]].push_back({i,R[i][0]});
    }    

    for(int i=0;i<n;i++){

        set<pair<int,int>>st;
        for(auto x:adj[i])
            st.insert(x);
        
        nxt[{i+INF*INF,0}] = (*st.begin()).S+(*st.begin()).F*INF;
        //printf("%d %d %d\n",i,nxt[{{i,INF},0}].F,nxt[{{i,INF},0}].S);

        for(auto x:adj[i]){
            st.erase(x);
            if(!st.empty()){
                pair<int,int>p = *st.begin();
                nxt[{i+x.F*INF,0}] = p.S+p.F*INF;
            }
            else 
                nxt[{i+x.F*INF,0}] = x.S+x.F*INF;
            //printf("%d %d 0 %d %d\n",i,x.F,nxt[{{i,x.F},0}].F,nxt[{{i,x.F},0}].S);
            st.insert(x);
        }
    }  

    for(int j=1;j<=30;j++)
        for(int i=0;i<n;i++){
            
            LL val = i+INF*INF;
            nxt[{val,j}] = nxt[{nxt[{val,j-1}],j-1}]; 

            for(auto x:adj[i]){
                LL val = i+x.F*INF;
                LL val1 = nxt[{val,j-1}];
                nxt[{val,j}] = nxt[{val1,j-1}];
                //printf("%d %d %d %d %d\n",i,x.S,j,nxt[{{i,x.S},j}].F,nxt[{{i,x.S},j}].S);
                continue;
            }
        }

    for(int i=0;i<Q;i++){
        int ans1 = 0;
        for(int j=0;j<n;j++){
            if(get_after(j,G[i])==P)ans1++;        
            //printf("%d %d\n",j,get_after(j,G[i]));
        }

        answer(ans1);
    }

}


/*
#define MAX_M  1000000
#define MAX_Q  2000

static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;

inline 
void my_assert(int e) {if (!e) abort();}
void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&P));
  for(i=0; i<M; i++)
    my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
  my_assert(1==scanf("%d",&Q));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&G[i]));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&solutions[i]));
}

void answer(int x)
{
  if(answer_count>=Q) {
    printf("Incorrect.  Too many answers.\n");
    exit(0);
  }
  answers[answer_count] = x;
  answer_count++;
}

int main()
{
  int correct, i;

  read_input();
  answer_count = 0;
  count_routes(N,M,P,R,Q,G);

  if(answer_count!=Q) {
    printf("Incorrect.  Too few answers.\n");
    exit(0);
  }

  correct = 1;
  for(i=0; i<Q; i++)
    if(answers[i]!=solutions[i])
      correct = 0;
  if(correct)
    printf("Correct.\n");
  else {
    printf("Incorrect.\n");
    printf("Expected: ");
    for(i=0; i<Q; i++)
      printf("%d ",solutions[i]);
    printf("\nReturned: ");
    for(i=0; i<Q; i++)
      printf("%d ",answers[i]);
  }
  return 0;
}
*/

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9540 KB Output is correct
2 Correct 38 ms 10512 KB Output is correct
3 Correct 42 ms 11204 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 89 ms 14660 KB Output is correct
7 Correct 8 ms 5708 KB Output is correct
8 Correct 42 ms 10864 KB Output is correct
9 Correct 484 ms 38364 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9540 KB Output is correct
2 Correct 38 ms 10512 KB Output is correct
3 Correct 42 ms 11204 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 89 ms 14660 KB Output is correct
7 Correct 8 ms 5708 KB Output is correct
8 Correct 42 ms 10864 KB Output is correct
9 Correct 484 ms 38364 KB Output is correct
10 Correct 8 ms 5580 KB Output is correct
11 Correct 1965 ms 137052 KB Output is correct
12 Runtime error 4816 ms 262148 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9540 KB Output is correct
2 Correct 38 ms 10512 KB Output is correct
3 Correct 42 ms 11204 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 89 ms 14660 KB Output is correct
7 Correct 8 ms 5708 KB Output is correct
8 Correct 42 ms 10864 KB Output is correct
9 Correct 484 ms 38364 KB Output is correct
10 Correct 8 ms 5580 KB Output is correct
11 Correct 1965 ms 137052 KB Output is correct
12 Runtime error 4816 ms 262148 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -