Submission #1202001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202001		dpsaveslives	Tropical Garden (IOI11_garden)	C++20	100 / 100	1382 ms	36564 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150005;
const int TMAX = 300005;
vector<int> adj[TMAX],radj[TMAX];
int nxt[TMAX];
int indeg[TMAX],sz[TMAX];
int dist0[MAXN],dist1[MAXN];
int cyc0[MAXN],cyc1[MAXN];
bool vis[TMAX];
vector<int> cyc;

void calc(int st, int *dist, int *cycs){
    memset(vis,false,sizeof(vis));
    queue<int> q, dq, cq;
    q.push(st); dq.push(0); cq.push(-1);
    dist[st] = 0; cycs[st] = -1; vis[st] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        int cd = dq.front(); dq.pop();
        int cc = cq.front(); cq.pop();
        cc = max(cc,sz[u]);
        if(u%2 == 0){
            dist[u/2] = cd;
            cycs[u/2] = cc;
        }
        for(auto v : radj[u]){
            if(!vis[v]){
                vis[v] = true;
                q.push(v);
                dq.push(cd+1);
                cq.push(cc);
            }
        }
    }
}
void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
    memset(dist0,-1,sizeof(dist0)); memset(dist1,-1,sizeof(dist1));
    memset(cyc0,-1,sizeof(cyc0)); memset(cyc1,-1,sizeof(cyc1));
    memset(sz,-1,sizeof(sz));
    for(int i = 0;i<M;++i){
        adj[R[i][0]].push_back(R[i][1]);
        adj[R[i][1]].push_back(R[i][0]);
    }
    for(int i = 0;i<N;++i){
        if(!adj[i].size()) continue;
        int v = adj[i][0];
        if(adj[v][0] != i){
            nxt[2*i] = 2*v;
        }
        else{
            nxt[2*i] = 2*v+1;
        }
        if(adj[i].size() == 1){
            nxt[2*i+1] = nxt[2*i];
        }
        else{
            int v2 = adj[i][1];
            if(adj[v2][0] != i){
                nxt[2*i+1] = 2*v2;
            }
            else{
                nxt[2*i+1] = 2*v2+1;
            }
        }
        //cout << 2*i << " " << nxt[2*i] << " " << 2*i+1 << " " << nxt[2*i+1] << "\n";
    }
    for(int i = 0;i<2*N;++i){
        ++indeg[i]; ++indeg[nxt[i]];
    }
    queue<int> q;
    for(int i = 0;i<2*N;++i){
        if(indeg[i] == 1) q.push(i);
    }
    while(!q.empty()){
        int u = q.front(); q.pop();
        --indeg[u]; --indeg[nxt[u]];
        if(indeg[nxt[u]] == 1) q.push(nxt[u]);
    }
    for(int i = 0;i<2*N;++i){
        radj[nxt[i]].push_back(i);
        if(indeg[i]){ //cycle
            cyc.clear(); int u = i;
            while(indeg[u]){
                indeg[u] = 0;
                //cout << u << " ";
                cyc.push_back(u);
                u = nxt[u];
            }
            //cout << "\n";
            for(auto x : cyc) sz[x] = cyc.size();
        }
    }
    calc(2*P,dist0,cyc0); calc(2*P+1,dist1,cyc1);
    for(int i = 0;i<Q;++i){
        int K = G[i], ans = 0;
        for(int u = 0;u<N;++u){
            if(dist0[u] != -1){
                if(cyc0[u] != -1){
                    if((K-dist0[u])%cyc0[u] == 0 && dist0[u] <= K){
                        ++ans;
                        continue;
                    }
                }
                else{
                    if(dist0[u] == K){
                        ++ans;
                        continue;
                    }
                }
            }
            if(dist1[u] != -1){
                if(cyc1[u]!= -1){
                    if((K-dist1[u])%cyc1[u] == 0 && dist1[u] <= K){
                        ++ans;
                        continue;
                    }
                }
                else{
                    if(dist1[u] == K){
                        ++ans;
                    }
                }
            }
        }
        answer(ans); 
    }
}

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