oj.uz

Submission #1022536

# Submission time Handle Problem Language Result Execution time Memory
1022536 2024-07-13T16:45:53 Z socpite Tropical Garden (IOI11_garden) C++17
49 / 100
 135 ms 176468 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;

vector<pair<int, int>> g_real[maxn];
vector<int> g[maxn];
vector<int> cyc[maxn];
int depcnt[maxn];

int ans[maxn];
int cycsz;

void dfs(int x, int rt, int dep, int N){
    if(x < N)depcnt[dep]++;
    for(auto v: g[x]){
        if(v == rt)cycsz = dep+1;
        else dfs(v, rt, dep+1, N);
    }
}

void solve(int N, int Q, int G[], int id){
    memset(depcnt, 0, sizeof(depcnt));
    cycsz = 0;
    for(int i = 0; i < maxn; i++)cyc[i].clear();

    dfs(id, id, 0, N);
    if(!cycsz)for(int i = 0; i < Q; i++)ans[i] += depcnt[G[i]];
    else {
        for(int i = 0; i < maxn; i++)while(depcnt[i]--)cyc[i%cycsz].push_back(i);
        for(int i = 0; i < Q; i++)ans[i] += upper_bound(cyc[G[i]%cycsz].begin(), cyc[G[i]%cycsz].end(), G[i]) - cyc[G[i]%cycsz].begin();
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    memset(ans, 0, sizeof(ans));
    for(int i = 0; i < 2*N; i++){
        g[i].clear();
        g_real[i].clear();
    }

    for(int i = 0; i < M; i++){
        g_real[R[i][0]].push_back({R[i][1], i});
        g_real[R[i][1]].push_back({R[i][0], i});
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < min(2, (int)g_real[i].size()); j++){
            int v = g_real[i][j].first, w = g_real[i][j].second;
            if(w == g_real[v][0].second && g_real[v].size() > 1){
                g[v+N].push_back(i + N*j);
            }
            else {
                g[v].push_back(i + N*j);
            }
        }
    }
    
    solve(N, Q, G, P);
    if(g_real[P].size() > 1)solve(N, Q, G, P+N);
    for(int i = 0; i < Q; i++)answer(ans[i]);
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 78676 KB Output is correct
2 Correct 39 ms 78684 KB Output is correct
3 Correct 41 ms 78680 KB Output is correct
4 Correct 40 ms 78676 KB Output is correct
5 Correct 39 ms 78672 KB Output is correct
6 Correct 38 ms 78932 KB Output is correct
7 Correct 39 ms 78676 KB Output is correct
8 Correct 41 ms 78672 KB Output is correct
9 Correct 45 ms 78932 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 78676 KB Output is correct
2 Correct 39 ms 78684 KB Output is correct
3 Correct 41 ms 78680 KB Output is correct
4 Correct 40 ms 78676 KB Output is correct
5 Correct 39 ms 78672 KB Output is correct
6 Correct 38 ms 78932 KB Output is correct
7 Correct 39 ms 78676 KB Output is correct
8 Correct 41 ms 78672 KB Output is correct
9 Correct 45 ms 78932 KB Output is correct
10 Correct 38 ms 78680 KB Output is correct
11 Correct 46 ms 80960 KB Output is correct
12 Correct 71 ms 82512 KB Output is correct
13 Correct 71 ms 98640 KB Output is correct
14 Correct 105 ms 90404 KB Output is correct
15 Correct 114 ms 91216 KB Output is correct
16 Correct 108 ms 88916 KB Output is correct
17 Runtime error 135 ms 176468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 78676 KB Output is correct
2 Correct 39 ms 78684 KB Output is correct
3 Correct 41 ms 78680 KB Output is correct
4 Correct 40 ms 78676 KB Output is correct
5 Correct 39 ms 78672 KB Output is correct
6 Correct 38 ms 78932 KB Output is correct
7 Correct 39 ms 78676 KB Output is correct
8 Correct 41 ms 78672 KB Output is correct
9 Correct 45 ms 78932 KB Output is correct
10 Correct 38 ms 78680 KB Output is correct
11 Correct 46 ms 80960 KB Output is correct
12 Correct 71 ms 82512 KB Output is correct
13 Correct 71 ms 98640 KB Output is correct
14 Correct 105 ms 90404 KB Output is correct
15 Correct 114 ms 91216 KB Output is correct
16 Correct 108 ms 88916 KB Output is correct
17 Runtime error 135 ms 176468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -