oj.uz

Submission #776183

# Submission time Handle Problem Language Result Execution time Memory
776183 2023-07-07T11:24:17 Z kirakaminski968 Tropical Garden (IOI11_garden) C++17
49 / 100
 37 ms 27624 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],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[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]){
                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));
    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 10 ms 17364 KB Output is correct
2 Correct 9 ms 17364 KB Output is correct
3 Correct 8 ms 17364 KB Output is correct
4 Correct 7 ms 17320 KB Output is correct
5 Correct 7 ms 17256 KB Output is correct
6 Correct 8 ms 17492 KB Output is correct
7 Correct 7 ms 17364 KB Output is correct
8 Correct 8 ms 17364 KB Output is correct
9 Correct 9 ms 17620 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17364 KB Output is correct
2 Correct 9 ms 17364 KB Output is correct
3 Correct 8 ms 17364 KB Output is correct
4 Correct 7 ms 17320 KB Output is correct
5 Correct 7 ms 17256 KB Output is correct
6 Correct 8 ms 17492 KB Output is correct
7 Correct 7 ms 17364 KB Output is correct
8 Correct 8 ms 17364 KB Output is correct
9 Correct 9 ms 17620 KB Output is correct
10 Correct 7 ms 17364 KB Output is correct
11 Correct 14 ms 19284 KB Output is correct
12 Correct 25 ms 21368 KB Output is correct
13 Incorrect 37 ms 27624 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17364 KB Output is correct
2 Correct 9 ms 17364 KB Output is correct
3 Correct 8 ms 17364 KB Output is correct
4 Correct 7 ms 17320 KB Output is correct
5 Correct 7 ms 17256 KB Output is correct
6 Correct 8 ms 17492 KB Output is correct
7 Correct 7 ms 17364 KB Output is correct
8 Correct 8 ms 17364 KB Output is correct
9 Correct 9 ms 17620 KB Output is correct
10 Correct 7 ms 17364 KB Output is correct
11 Correct 14 ms 19284 KB Output is correct
12 Correct 25 ms 21368 KB Output is correct
13 Incorrect 37 ms 27624 KB Output isn't correct
14 Halted 0 ms 0 KB -