oj.uz

Submission #776189

# Submission time Handle Problem Language Result Execution time Memory
776189 2023-07-07T11:31:45 Z kirakaminski968 Tropical Garden (IOI11_garden) C++17
49 / 100
 37 ms 25848 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){
    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 15060 KB Output is correct
2 Correct 7 ms 15108 KB Output is correct
3 Correct 7 ms 15128 KB Output is correct
4 Correct 6 ms 15024 KB Output is correct
5 Correct 6 ms 14932 KB Output is correct
6 Correct 9 ms 15248 KB Output is correct
7 Correct 6 ms 14932 KB Output is correct
8 Correct 7 ms 15060 KB Output is correct
9 Correct 8 ms 15316 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15060 KB Output is correct
2 Correct 7 ms 15108 KB Output is correct
3 Correct 7 ms 15128 KB Output is correct
4 Correct 6 ms 15024 KB Output is correct
5 Correct 6 ms 14932 KB Output is correct
6 Correct 9 ms 15248 KB Output is correct
7 Correct 6 ms 14932 KB Output is correct
8 Correct 7 ms 15060 KB Output is correct
9 Correct 8 ms 15316 KB Output is correct
10 Correct 6 ms 14932 KB Output is correct
11 Correct 16 ms 17236 KB Output is correct
12 Correct 31 ms 19132 KB Output is correct
13 Incorrect 37 ms 25848 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15060 KB Output is correct
2 Correct 7 ms 15108 KB Output is correct
3 Correct 7 ms 15128 KB Output is correct
4 Correct 6 ms 15024 KB Output is correct
5 Correct 6 ms 14932 KB Output is correct
6 Correct 9 ms 15248 KB Output is correct
7 Correct 6 ms 14932 KB Output is correct
8 Correct 7 ms 15060 KB Output is correct
9 Correct 8 ms 15316 KB Output is correct
10 Correct 6 ms 14932 KB Output is correct
11 Correct 16 ms 17236 KB Output is correct
12 Correct 31 ms 19132 KB Output is correct
13 Incorrect 37 ms 25848 KB Output isn't correct
14 Halted 0 ms 0 KB -