oj.uz

Submission #776191

# Submission time Handle Problem Language Result Execution time Memory
776191 2023-07-07T11:39:50 Z kirakaminski968 Tropical Garden (IOI11_garden) C++17
100 / 100
 2324 ms 35484 KB 
#include "garden.h"
#include "gardenlib.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];
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[150005],dist1[150005],peri0[150005],peri1[150005];
void finddist(int tar, int *dist, int *per){
    memset(vis,false,sizeof(vis)); 
    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]){
                vis[i] = true; 
                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(sizes,-1,sizeof(sizes));
    memset(dist0,-1,sizeof(dist0));
    memset(dist1,-1,sizeof(dist1));
    memset(peri0,-1,sizeof(peri0)); 
    memset(peri1,-1,sizeof(peri1)); 
    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!
            cycles.clear(); 
            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);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15316 KB Output is correct
2 Correct 7 ms 15316 KB Output is correct
3 Correct 7 ms 15348 KB Output is correct
4 Correct 6 ms 15196 KB Output is correct
5 Correct 6 ms 15188 KB Output is correct
6 Correct 7 ms 15444 KB Output is correct
7 Correct 6 ms 15228 KB Output is correct
8 Correct 7 ms 15316 KB Output is correct
9 Correct 8 ms 15532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15316 KB Output is correct
2 Correct 7 ms 15316 KB Output is correct
3 Correct 7 ms 15348 KB Output is correct
4 Correct 6 ms 15196 KB Output is correct
5 Correct 6 ms 15188 KB Output is correct
6 Correct 7 ms 15444 KB Output is correct
7 Correct 6 ms 15228 KB Output is correct
8 Correct 7 ms 15316 KB Output is correct
9 Correct 8 ms 15532 KB Output is correct
10 Correct 6 ms 15316 KB Output is correct
11 Correct 14 ms 17624 KB Output is correct
12 Correct 29 ms 19276 KB Output is correct
13 Correct 36 ms 25888 KB Output is correct
14 Correct 72 ms 29936 KB Output is correct
15 Correct 83 ms 30360 KB Output is correct
16 Correct 60 ms 26956 KB Output is correct
17 Correct 70 ms 26180 KB Output is correct
18 Correct 24 ms 19796 KB Output is correct
19 Correct 67 ms 29836 KB Output is correct
20 Correct 80 ms 30448 KB Output is correct
21 Correct 65 ms 26884 KB Output is correct
22 Correct 62 ms 26108 KB Output is correct
23 Correct 86 ms 31076 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15316 KB Output is correct
2 Correct 7 ms 15316 KB Output is correct
3 Correct 7 ms 15348 KB Output is correct
4 Correct 6 ms 15196 KB Output is correct
5 Correct 6 ms 15188 KB Output is correct
6 Correct 7 ms 15444 KB Output is correct
7 Correct 6 ms 15228 KB Output is correct
8 Correct 7 ms 15316 KB Output is correct
9 Correct 8 ms 15532 KB Output is correct
10 Correct 6 ms 15316 KB Output is correct
11 Correct 14 ms 17624 KB Output is correct
12 Correct 29 ms 19276 KB Output is correct
13 Correct 36 ms 25888 KB Output is correct
14 Correct 72 ms 29936 KB Output is correct
15 Correct 83 ms 30360 KB Output is correct
16 Correct 60 ms 26956 KB Output is correct
17 Correct 70 ms 26180 KB Output is correct
18 Correct 24 ms 19796 KB Output is correct
19 Correct 67 ms 29836 KB Output is correct
20 Correct 80 ms 30448 KB Output is correct
21 Correct 65 ms 26884 KB Output is correct
22 Correct 62 ms 26108 KB Output is correct
23 Correct 86 ms 31076 KB Output is correct
24 Correct 7 ms 15316 KB Output is correct
25 Correct 78 ms 17876 KB Output is correct
26 Correct 112 ms 19964 KB Output is correct
27 Correct 2041 ms 26992 KB Output is correct
28 Correct 780 ms 30028 KB Output is correct
29 Correct 2324 ms 30500 KB Output is correct
30 Correct 1297 ms 27004 KB Output is correct
31 Correct 1308 ms 26260 KB Output is correct
32 Correct 119 ms 19840 KB Output is correct
33 Correct 780 ms 30104 KB Output is correct
34 Correct 2317 ms 30464 KB Output is correct
35 Correct 1391 ms 26952 KB Output is correct
36 Correct 1330 ms 26160 KB Output is correct
37 Correct 650 ms 31240 KB Output is correct
38 Correct 1790 ms 35484 KB Output is correct