Submission #776177

#	Time	Username	Problem	Language	Result	Execution time	Memory
776177		kirakaminski968	Tropical Garden (IOI11_garden)	C++17	Compilation error	0 ms	0 KiB

garden

#include "garden.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> graph[150005]; //just the normal graph
vector<int> adj[300005],cycles; //the graph with only one outgoing edge and each node twice
int best[150005],outgoing[300005],deg[300005],sizes[300005];
bool vis[300005],ans[300005];
void constructgraph(int N, int M, int R[][2]){
    for(int i = 0;i<M;++i){
        best[R[i][0]] = min(best[R[i][0]],i); //save the best trails for each node!
        best[R[i][1]] = min(best[R[i][1]],i);
        graph[R[i][0]].push_back({R[i][1],i}); //it's in decreasing order
        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] = graph[i][0].first*2+1;
        else outgoing[2*i] = graph[i][0].first*2;
        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] = graph[i][1].first*2+1;
            else outgoing[2*i+1] = graph[i][1].first*2;
        }
    }
}
int dist0[15005],dist1[15005],peri0[15005],peri1[15005];
void finddist(int tar, int *dist, int *per){
    queue<int> q,nq,nnq;
    q.push(tar); nq.push(-1); nnq.push(0);
    vis[tar] = true;
    while(!q.empty()){
        int qf = q.front(); q.pop();
        int nqf = nq.front(); nq.pop();
        int cdist = nnq.front(); nnq.pop();
        nqf = max(nqf,sizes[qf]);
        if(qf % 2 == 0){
            dist[qf/2] = cdist;
            per[qf/2] = nqf;
        }
        for(auto i : adj[qf]){
            if(!vis[i]){
                q.push(i);
                nq.push(nqf);
                nnq.push(cdist+1);
            }
        }
     }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    memset(best,0x3f,sizeof(best));
    memset(deg,0,sizeof(deg));
    memset(outgoing,0,sizeof(outgoing));
    memset(sizes,-1,sizeof(sizes));
    memset(dist0,-1,sizeof(dist0));
    memset(dist1,-1,sizeof(dist1));
    constructgraph(N,M,R);
    //we need to find the cycles! Kahn's Algorithm?
    for(int i = 0;i<2*N;++i){
        deg[i]++;
        deg[outgoing[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!
            int cur = i;
            while(deg[cur]){
                deg[cur] = 0;
                cycles.push_back(cur);
                cur = outgoing[cur];
            }
            for(auto i : cycles) sizes[i] = (int)cycles.size();
        }
    }
    //We still have to figure out the distances
    finddist(2*P, dist0, peri0); finddist(2*P+1,dist1,peri1);
    for(int i = 0;i<Q;++i){
        int cnt = 0;
        for(int j = 0;j<N;++j){
            if(dist0[j] != -1){
                if(peri0[j] == -1){
                    if(dist0[j] == G[i]){
                        cnt++; continue;
                    }
                }
                else{
                    if((G[i]-dist0[j])%peri0[j] == 0 && dist0[j]<=G[i]){
                        cnt++; continue;
                    }
                }
            }
            if(dist1[j] != -1){
                if(peri1[j] == -1){
                    if(dist1[j] == G[i]){
                        cnt++; continue;
                    }
                }
                else{
                    if((G[i]-dist1[j])%peri1[j] == 0 && dist1[j]<=G[i]){
                        cnt++; continue;
                    }
                }
            }
        }
        answer(cnt);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:114:9: error: 'answer' was not declared in this scope
  114 |         answer(cnt);
      |         ^~~~~~