oj.uz

Submission #776186

# Submission time Handle Problem Language Result Execution time Memory
776186 2023-07-07T11:27:54 Z kirakaminski968 Tropical Garden (IOI11_garden) C++17
49 / 100
 45 ms 26784 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]){
                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(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 17448 KB Output is correct
2 Correct 7 ms 17448 KB Output is correct
3 Correct 7 ms 17444 KB Output is correct
4 Correct 7 ms 17364 KB Output is correct
5 Correct 7 ms 17240 KB Output is correct
6 Correct 8 ms 17436 KB Output is correct
7 Correct 8 ms 17300 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 7 ms 17448 KB Output is correct
2 Correct 7 ms 17448 KB Output is correct
3 Correct 7 ms 17444 KB Output is correct
4 Correct 7 ms 17364 KB Output is correct
5 Correct 7 ms 17240 KB Output is correct
6 Correct 8 ms 17436 KB Output is correct
7 Correct 8 ms 17300 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 15 ms 19284 KB Output is correct
12 Correct 30 ms 20860 KB Output is correct
13 Incorrect 45 ms 26784 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 17448 KB Output is correct
2 Correct 7 ms 17448 KB Output is correct
3 Correct 7 ms 17444 KB Output is correct
4 Correct 7 ms 17364 KB Output is correct
5 Correct 7 ms 17240 KB Output is correct
6 Correct 8 ms 17436 KB Output is correct
7 Correct 8 ms 17300 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 15 ms 19284 KB Output is correct
12 Correct 30 ms 20860 KB Output is correct
13 Incorrect 45 ms 26784 KB Output isn't correct
14 Halted 0 ms 0 KB -