oj.uz

답안 #573189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
573189 2022-06-06T08:37:59 Z dooompy 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
49 / 100
 49 ms 19656 KB 
 
#include <bits/stdc++.h>
#include "garden.h"
 
using namespace std;
 
typedef long long ll;
 
void answer (int x);
 
void count_routes (int N, int M, int P, int R[][2], int Q, int G[])
{
    vector <vector <int>> adj (N);
    for(int i = 0; i < M; i++)
    {
        adj[R[i][0]].push_back(R[i][1]);
        adj[R[i][1]].push_back(R[i][0]);
    }
 
    vector <int> edge (N * 2);
    for(int u = 0; u < N; u++)
    {
        edge[u] = adj[u][0];
        if(adj[edge[u]][0] == u)
            edge[u] += N;
    }
    for(int u = 0; u < N; u++)
    {
        if((int) adj[u].size() >= 2)
            edge[N + u] = adj[u][1];
        else
            edge[N + u] = adj[u][0];
 
        if(adj[edge[N + u]][0] == u)
            edge[N + u] += N;
    }
 
    vector <vector <int>> rev (N * 2);
    for(int u = 0; u < N * 2; u++)
        rev[edge[u]].push_back(u);
 
    function <void (int, vector <int> &, int&)> bfs = [&] (int start, vector <int> &dist, int &cycle)
    {
        dist = vector <int> (N * 2, INT_MAX);
 
        queue <int> q;
 
        q.push(start);
        dist[start] = 0;
 
        while(q.empty() == false)
        {
            int u = q.front();
            q.pop();
 
            for(int v : rev[u])
                if(dist[v] == INT_MAX)
                {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
        }
 
        cycle = 0;
        vector <bool> seen (N * 2, false);
        int u = start;
        while(seen[u] == false)
        {
            cycle++;
            seen[u] = true;
            u = edge[u];
        }
 
        if(u != start || cycle == 1)
            cycle = INT_MAX;
    };
 
    vector <int> distA, distB;
    int cycleA, cycleB;
 
    bfs(P, distA, cycleA);
    bfs(N + P, distB, cycleB);
 
    vector <int> vecA, vecB;
    for(int u = 0; u < N; u++)
    {
        if(distA[u] != INT_MAX)
            vecA.push_back(distA[u]);
        else if(distB[u] != INT_MAX)
            vecB.push_back(distB[u]);
    }
 
    sort(vecA.begin(), vecA.end(), greater <int> ());
    sort(vecB.begin(), vecB.end(), greater <int> ());
 
    vector <int> perm (Q);
    for(int i = 0; i < Q; i++)
        perm[i] = i;
    sort(perm.begin(), perm.end(),
         [&] (const int &i, const int &j)
         {
             return G[i] < G[j];
         });
 
    vector <int> ans (Q);
 
    vector <int> cntA (N * 2, 0);
    vector <int> cntB (N * 2, 0);
 
    for(int x = 0; x < Q; x++)
    {
        int i = perm[x];
 
        while(vecA.empty() == false && vecA.back() <= G[i])
        {
            cntA[vecA.back() % cycleA]++;
            vecA.pop_back();
        }
        while(vecB.empty() == false && vecB.back() <= G[i])
        {
            cntB[vecB.back() % cycleB]++;
            vecB.pop_back();
        }
 
        if(G[i] % cycleA < N * 2)
            ans[i] += cntA[G[i] % cycleA];
        if(G[i] % cycleB < N * 2)
            ans[i] += cntB[G[i] % cycleB];
    }
 
    for(int i = 0; i < Q; i++)
        answer(ans[i]);
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 596 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 11 ms 4820 KB Output is correct
12 Correct 25 ms 8020 KB Output is correct
13 Incorrect 49 ms 19656 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 11 ms 4820 KB Output is correct
12 Correct 25 ms 8020 KB Output is correct
13 Incorrect 49 ms 19656 KB Output isn't correct
14 Halted 0 ms 0 KB -