oj.uz

Submission #1022534

# Submission time Handle Problem Language Result Execution time Memory
1022534 2024-07-13T16:44:25 Z socpite Tropical Garden (IOI11_garden) C++14
49 / 100
 140 ms 175444 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 78680 KB Output is correct
2 Correct 42 ms 78632 KB Output is correct
3 Correct 39 ms 78672 KB Output is correct
4 Correct 36 ms 78684 KB Output is correct
5 Correct 37 ms 78688 KB Output is correct
6 Correct 48 ms 78932 KB Output is correct
7 Correct 48 ms 78572 KB Output is correct
8 Correct 39 ms 78672 KB Output is correct
9 Correct 39 ms 78940 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 78680 KB Output is correct
2 Correct 42 ms 78632 KB Output is correct
3 Correct 39 ms 78672 KB Output is correct
4 Correct 36 ms 78684 KB Output is correct
5 Correct 37 ms 78688 KB Output is correct
6 Correct 48 ms 78932 KB Output is correct
7 Correct 48 ms 78572 KB Output is correct
8 Correct 39 ms 78672 KB Output is correct
9 Correct 39 ms 78940 KB Output is correct
10 Correct 38 ms 78680 KB Output is correct
11 Correct 45 ms 80732 KB Output is correct
12 Correct 54 ms 82000 KB Output is correct
13 Correct 70 ms 98044 KB Output is correct
14 Correct 103 ms 89424 KB Output is correct
15 Correct 109 ms 90176 KB Output is correct
16 Correct 97 ms 87892 KB Output is correct
17 Runtime error 140 ms 175444 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 78680 KB Output is correct
2 Correct 42 ms 78632 KB Output is correct
3 Correct 39 ms 78672 KB Output is correct
4 Correct 36 ms 78684 KB Output is correct
5 Correct 37 ms 78688 KB Output is correct
6 Correct 48 ms 78932 KB Output is correct
7 Correct 48 ms 78572 KB Output is correct
8 Correct 39 ms 78672 KB Output is correct
9 Correct 39 ms 78940 KB Output is correct
10 Correct 38 ms 78680 KB Output is correct
11 Correct 45 ms 80732 KB Output is correct
12 Correct 54 ms 82000 KB Output is correct
13 Correct 70 ms 98044 KB Output is correct
14 Correct 103 ms 89424 KB Output is correct
15 Correct 109 ms 90176 KB Output is correct
16 Correct 97 ms 87892 KB Output is correct
17 Runtime error 140 ms 175444 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -