oj.uz

Submission #573189

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -