Submission #392462

#	Time	Username	Problem	Language	Result	Execution time	Memory
392462		Hazem	Tropical Garden (IOI11_garden)	C++14	49 / 100	4749 ms	262148 KiB

garden

#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 {
            
            if(nxt.find({i+pre*INF,j})==nxt.end()){
                while(1)j *= INF;
            }
            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_c ount;

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 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31