oj.uz

답안 #776189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -