Submission #813282

#	Time	Username	Problem	Language	Result	Execution time	Memory
813282		annabeth9680	Tropical Garden (IOI11_garden)	C++17	100 / 100	2360 ms	35368 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int,int>> graph[150005];
vector<int> adj[300005],cycle;
int best[150005],outgoing[300005],deg[300005],sizes[300005]; 
int dist0[150005],dist1[150005],peri0[150005],peri1[150005];
bool vis[300005];
void build(int N, int M, int R[][2]){
    for(int i = 0;i<M;++i){
        best[R[i][0]] = min(best[R[i][0]],i);
        best[R[i][1]] = min(best[R[i][1]],i);
        graph[R[i][0]].push_back({R[i][1],i});
        graph[R[i][1]].push_back({R[i][0],i});
    }
    for(int i = 0;i<N;++i){
        if(best[graph[i][0].first] == graph[i][0].second) outgoing[2*i] = 2*graph[i][0].first+1;
        else outgoing[2*i] = 2*graph[i][0].first;
        if(graph[i].size() == 1) outgoing[2*i+1] = outgoing[2*i];
        else{
            if(best[graph[i][1].first] == graph[i][1].second) outgoing[2*i+1] = 2*graph[i][1].first+1;
            else outgoing[2*i+1] = 2*graph[i][1].first;
        }
    }
}
void calcdist(int src, int* dist, int* peri){
    memset(vis,false,sizeof(vis));
    queue<int> q,dq,pq; q.push(src); vis[src] = true;
    dq.push(0); pq.push(-1);
    while(!q.empty()){
        int u = q.front(); q.pop();
        int curdist = dq.front(); dq.pop();
        int curper = pq.front(); pq.pop();
        curper = max(curper,sizes[u]);
        if(u % 2 == 0){
            dist[u/2] = curdist;
            peri[u/2] = curper;
        }
        for(auto v : adj[u]){
            if(!vis[v]){
                vis[v] = true;
                q.push(v); dq.push(curdist+1);
                pq.push(curper);
            }
        }
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    memset(best,0x3f,sizeof(best));
    memset(sizes,-1,sizeof(sizes));
    memset(peri0,-1,sizeof(peri0));
    memset(peri1,-1,sizeof(peri1));
    memset(dist0,-1,sizeof(dist0));
    memset(dist1,-1,sizeof(dist1));
    build(N,M,R);
    for(int i = 0;i<2*N;++i){
        deg[outgoing[i]]++;
        deg[i]++;
    }
    queue<int> q;
    for(int i = 0;i<2*N;++i){
        if(deg[i] == 1) q.push(i);
    }
    while(!q.empty()){
        int u = q.front(); q.pop();
        deg[u]--; deg[outgoing[u]]--;
        if(deg[outgoing[u]] == 1){
            q.push(outgoing[u]);
        }
    }
    for(int i = 0;i<2*N;++i){
        adj[outgoing[i]].push_back(i);
        if(deg[i]){
            cycle.clear(); int v = i;
            while(deg[v]){
                deg[v] = 0; cycle.push_back(v);
                v = outgoing[v];
            }
            for(auto c : cycle) sizes[c] = (int)cycle.size();
        }
    }
    calcdist(2*P,dist0,peri0); calcdist(2*P+1,dist1,peri1);
    for(int i = 0;i<Q;++i){
        int K = G[i], cnt = 0;
        for(int j = 0;j<N;++j){
            if(dist0[j] != -1){
                if(peri0[j] == -1){
                    if(dist0[j] == K){
                        cnt++;
                        continue;
                    }
                }
                else{
                    if((K-dist0[j])%peri0[j] == 0 && dist0[j] <= K){
                        cnt++;
                        continue;
                    }
                }
            }
            if(dist1[j] != -1){
                if(peri1[j] == -1){
                    if(dist1[j] == K){
                        cnt++;
                        continue;
                    }
                }
                else{
                    if((K-dist1[j])%peri1[j] == 0 && dist1[j] <= K){
                        cnt++;
                        continue;
                    }
                }
            }
        }
        answer(cnt); 
    }
}

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