oj.uz

Submission #776181

# Submission time Handle Problem Language Result Execution time Memory
776181 2023-07-07T11:18:27 Z kirakaminski968 Tropical Garden (IOI11_garden) C++17
49 / 100
 28 ms 34900 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[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));
    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 9 ms 15248 KB Output is correct
3 Correct 8 ms 15248 KB Output is correct
4 Correct 6 ms 15232 KB Output is correct
5 Correct 6 ms 15176 KB Output is correct
6 Correct 7 ms 15384 KB Output is correct
7 Correct 6 ms 15188 KB Output is correct
8 Correct 6 ms 15256 KB Output is correct
9 Correct 9 ms 15568 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15316 KB Output is correct
2 Correct 9 ms 15248 KB Output is correct
3 Correct 8 ms 15248 KB Output is correct
4 Correct 6 ms 15232 KB Output is correct
5 Correct 6 ms 15176 KB Output is correct
6 Correct 7 ms 15384 KB Output is correct
7 Correct 6 ms 15188 KB Output is correct
8 Correct 6 ms 15256 KB Output is correct
9 Correct 9 ms 15568 KB Output is correct
10 Correct 7 ms 15188 KB Output is correct
11 Runtime error 28 ms 34900 KB Execution killed with signal 8
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15316 KB Output is correct
2 Correct 9 ms 15248 KB Output is correct
3 Correct 8 ms 15248 KB Output is correct
4 Correct 6 ms 15232 KB Output is correct
5 Correct 6 ms 15176 KB Output is correct
6 Correct 7 ms 15384 KB Output is correct
7 Correct 6 ms 15188 KB Output is correct
8 Correct 6 ms 15256 KB Output is correct
9 Correct 9 ms 15568 KB Output is correct
10 Correct 7 ms 15188 KB Output is correct
11 Runtime error 28 ms 34900 KB Execution killed with signal 8
12 Halted 0 ms 0 KB -