oj.uz

Submission #1022537

# Submission time Handle Problem Language Result Execution time Memory
1022537 2024-07-13T16:47:38 Z socpite Tropical Garden (IOI11_garden) C++14
49 / 100
 89 ms 64340 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){
    assert(dep < maxn);
    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 23900 KB Output is correct
2 Correct 13 ms 24048 KB Output is correct
3 Correct 11 ms 23860 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 11 ms 23796 KB Output is correct
6 Correct 11 ms 24156 KB Output is correct
7 Correct 13 ms 23900 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 23900 KB Output is correct
2 Correct 13 ms 24048 KB Output is correct
3 Correct 11 ms 23860 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 11 ms 23796 KB Output is correct
6 Correct 11 ms 24156 KB Output is correct
7 Correct 13 ms 23900 KB Output is correct
8 Correct 12 ms 23900 KB Output is correct
9 Correct 13 ms 24156 KB Output is correct
10 Correct 12 ms 23896 KB Output is correct
11 Correct 17 ms 25868 KB Output is correct
12 Correct 28 ms 27152 KB Output is correct
13 Correct 47 ms 43088 KB Output is correct
14 Correct 65 ms 34620 KB Output is correct
15 Correct 71 ms 35452 KB Output is correct
16 Correct 72 ms 33104 KB Output is correct
17 Runtime error 89 ms 64340 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 23900 KB Output is correct
2 Correct 13 ms 24048 KB Output is correct
3 Correct 11 ms 23860 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 11 ms 23796 KB Output is correct
6 Correct 11 ms 24156 KB Output is correct
7 Correct 13 ms 23900 KB Output is correct
8 Correct 12 ms 23900 KB Output is correct
9 Correct 13 ms 24156 KB Output is correct
10 Correct 12 ms 23896 KB Output is correct
11 Correct 17 ms 25868 KB Output is correct
12 Correct 28 ms 27152 KB Output is correct
13 Correct 47 ms 43088 KB Output is correct
14 Correct 65 ms 34620 KB Output is correct
15 Correct 71 ms 35452 KB Output is correct
16 Correct 72 ms 33104 KB Output is correct
17 Runtime error 89 ms 64340 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -