Submission #1269371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269371		AlgorithmWarrior	Tropical Garden (IOI11_garden)	C++20	100 / 100	74 ms	32436 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

int const NMAX=150005;
int const INF=1e9;

struct edge{
    int id,to;
}edges[NMAX][2];

int func[2*NMAX];
vector<int>GR[2*NMAX];
int dist0[2*NMAX],dist1[2*NMAX];

void bfs(int nod,int dist[],int n){
    queue<int>q;
    int i;
    for(i=0;i<2*n;++i)
        dist[i]=INF;
    dist[nod]=0;
    q.push(nod);
    while(!q.empty()){
        int fr=q.front();
        q.pop();
        for(auto vec : GR[fr])
            if(dist[vec]==INF){
                dist[vec]=dist[fr]+1;
                q.push(vec);
            }
    }
}

bool viz[2*NMAX];
struct destinatie{
    int unde,pasi;
}dest[2];

void dfs(int nod,int n,int p,int comp){
    int i;
    for(i=0;i<2*n;++i)
        viz[i]=0;
    viz[nod]=1;
    nod=func[nod];
    int nrp=1;
    while(!viz[nod] && nod!=2*p && nod!=2*p+1){
        viz[nod]=1;
        nod=func[nod];
        ++nrp;
    }
    if(nod!=2*p && nod!=2*p+1)
        dest[comp].unde=2;
    else
        dest[comp].unde=nod%2;
    dest[comp].pasi=nrp;
}

map<int,int>supl;
map<int,int>cic1;
map<int,int>cic2;
map<int,int>cic3;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i;
    for(i=0;i<N;++i)
        edges[i][0]=edges[i][1]={-1,-1};
    for(i=0;i<M;++i){
        int nod1=R[i][0];
        int nod2=R[i][1];
        if(edges[nod1][0].id==-1)
            edges[nod1][0]={i,nod2};
        else
            if(edges[nod1][1].id==-1)
                edges[nod1][1]={i,nod2};
        if(edges[nod2][0].id==-1)
            edges[nod2][0]={i,nod1};
        else
            if(edges[nod2][1].id==-1)
                edges[nod2][1]={i,nod1};
    }
    for(i=0;i<2*N;++i){
        int nod=i/2;
        int tip=i%2;
        if(tip==0 || (tip==1 && edges[nod][1].id==-1))
            func[i]=2*edges[nod][0].to+(edges[edges[nod][0].to][0].id==edges[nod][0].id);
        else
            func[i]=2*edges[nod][1].to+(edges[edges[nod][1].to][0].id==edges[nod][1].id);
        GR[func[i]].push_back(i);
    }
    bfs(2*P,dist0,N);
    bfs(2*P+1,dist1,N);
    dfs(2*P,N,P,0);
    dfs(2*P+1,N,P,1);
    vector<pair<int,int>>baleiere;
    for(i=0;i<2*N;i+=2){
        if(dist0[i]==INF && dist1[i]==INF)
            continue;
        if(dist0[i]<dist1[i]){
            if(dest[0].unde==2)
                ++supl[dist0[i]];
            else
                if(dest[0].unde==0)
                    baleiere.push_back({dist0[i],-1});
                else{
                    if(dest[1].unde==2){
                        ++supl[dist0[i]];
                        ++supl[dist1[i]];
                    }
                    else
                        if(dest[1].unde==1){
                            ++supl[dist0[i]];
                            baleiere.push_back({dist1[i],-2});
                        }
                        else
                            baleiere.push_back({dist0[i],-3});
                }
        }
        else{
            if(dest[1].unde==2)
                ++supl[dist1[i]];
            else
                if(dest[1].unde==1)
                    baleiere.push_back({dist1[i],-2});
                else{
                    if(dest[0].unde==2){
                        ++supl[dist0[i]];
                        ++supl[dist1[i]];
                    }
                    else
                        if(dest[0].unde==0){
                            ++supl[dist1[i]];
                            baleiere.push_back({dist0[i],-1});
                        }
                        else
                            baleiere.push_back({dist1[i],-4});
                }
        }
    }
    for(i=0;i<Q;++i)
        baleiere.push_back({G[i],i});
    sort(baleiere.begin(),baleiere.end());
    vector<int>ans(Q);
    for(auto [pasi,tip] : baleiere){
        if(tip>=0){
            ans[tip]=supl[pasi];
            if(dest[0].unde==0)
                ans[tip]+=cic1[pasi%dest[0].pasi];
            if(dest[1].unde==1)
                ans[tip]+=cic2[pasi%dest[1].pasi];
            if(dest[0].unde==1 && dest[1].unde==0)
                ans[tip]+=cic3[pasi%(dest[0].pasi+dest[1].pasi)];
        }
        else{
            if(tip==-1)
                ++cic1[pasi%dest[0].pasi];
            if(tip==-2)
                ++cic2[pasi%dest[1].pasi];
            if(tip==-3){
                ++cic3[pasi%(dest[0].pasi+dest[1].pasi)];
                ++cic3[(pasi+dest[0].pasi)%(dest[0].pasi+dest[1].pasi)];
            }
            if(tip==-4){
                ++cic3[pasi%(dest[0].pasi+dest[1].pasi)];
                ++cic3[(pasi+dest[1].pasi)%(dest[0].pasi+dest[1].pasi)];
            }
        }
    }
    for(i=0;i<Q;++i)
        answer(ans[i]);
}

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