Submission #900539

#	Time	Username	Problem	Language	Result	Execution time	Memory
900539		JakobZorz	Tropical Garden (IOI11_garden)	C++17	100 / 100	3739 ms	19740 KiB

garden

#include"garden.h"
#include"gardenlib.h"
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int n; // num nodes
int m; // num edges
vector<vector<int>>nodes; // lowest node and second lowest node
vector<int>nxt;
vector<int>vis;
vector<int>dist;
int cycle_size;

void add_conn(int node,int dest){
    if(nodes[node][0]==-1){
        nodes[node]={dest,dest};
    }else if(nodes[node][0]==nodes[node][1]){
        nodes[node][1]=dest;
    }
}

void dfs(int node){
    if(vis[nxt[node]]!=-1){
        if(vis[nxt[node]]==0)
            cycle_size=vis[node]+1;
        else
            cycle_size=-1;
        return;
    }
    vis[nxt[node]]=vis[node]+1;
    dfs(nxt[node]);
}

int get_dist(int node){
    if(dist[node]!=-1)
        return dist[node];
    dist[node]=1e9;
    dist[node]=get_dist(nxt[node])+1;
    return dist[node];
}

vector<int>get(int Q,int G[],int P){
    vis=vector<int>(2*n,-1);
    vis[P]=0;
    dfs(P);
    dist=vector<int>(2*n,-1);
    dist[P]=0;
    vector<int>res(Q);
    if(cycle_size==-1){
        unordered_map<int,int>mp;
        for(int i=0;i<n;i++)
            mp[get_dist(2*i)]++;
        
        for(int i=0;i<Q;i++)
            res[i]+=mp[G[i]];
    }else{
        for(int i=0;i<Q;i++){
            for(int j=0;j<n;j++){
                int dist=get_dist(2*j);
                if(dist<=G[i]&&dist%cycle_size==G[i]%cycle_size){
                    res[i]++;
                }
            }
        }
    }
    return res;
}

void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
    n=N;
    m=M;
    nodes=vector<vector<int>>(n,{-1,-1});
    nxt.resize(2*n);
    for(int i=0;i<m;i++){
        add_conn(R[i][0],R[i][1]);
        add_conn(R[i][1],R[i][0]);
    }
    
    for(int i=0;i<2*n;i++){
        nxt[i]=2*nodes[i/2][i%2];
        if(nodes[nxt[i]/2][0]==i/2&&nodes[nxt[i]/2][1]!=-1)
            nxt[i]++;
    }
    
    vector<int>res1=get(Q,G,2*P);
    vector<int>res2=get(Q,G,2*P+1);
    
    for(int i=0;i<Q;i++){
        answer(res1[i]+res2[i]);
    }
}

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