oj.uz

Submission #1022533

# Submission time Handle Problem Language Result Execution time Memory
1022533 2024-07-13T16:43:42 Z socpite Tropical Garden (IOI11_garden) C++14
49 / 100
 89 ms 65756 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5+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 12 ms 24152 KB Output is correct
2 Correct 12 ms 23896 KB Output is correct
3 Correct 12 ms 24056 KB Output is correct
4 Correct 11 ms 23752 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 13 ms 23968 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 12 ms 23900 KB Output is correct
9 Correct 13 ms 24156 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24152 KB Output is correct
2 Correct 12 ms 23896 KB Output is correct
3 Correct 12 ms 24056 KB Output is correct
4 Correct 11 ms 23752 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 13 ms 23968 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 12 ms 23900 KB Output is correct
9 Correct 13 ms 24156 KB Output is correct
10 Correct 11 ms 23896 KB Output is correct
11 Correct 17 ms 26068 KB Output is correct
12 Correct 26 ms 27796 KB Output is correct
13 Correct 44 ms 44372 KB Output is correct
14 Correct 89 ms 36176 KB Output is correct
15 Correct 74 ms 37216 KB Output is correct
16 Correct 65 ms 34640 KB Output is correct
17 Runtime error 74 ms 65756 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 12 ms 24152 KB Output is correct
2 Correct 12 ms 23896 KB Output is correct
3 Correct 12 ms 24056 KB Output is correct
4 Correct 11 ms 23752 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 13 ms 23968 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 12 ms 23900 KB Output is correct
9 Correct 13 ms 24156 KB Output is correct
10 Correct 11 ms 23896 KB Output is correct
11 Correct 17 ms 26068 KB Output is correct
12 Correct 26 ms 27796 KB Output is correct
13 Correct 44 ms 44372 KB Output is correct
14 Correct 89 ms 36176 KB Output is correct
15 Correct 74 ms 37216 KB Output is correct
16 Correct 65 ms 34640 KB Output is correct
17 Runtime error 74 ms 65756 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -