Submission #1022536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022536		socpite	Tropical Garden (IOI11_garden)	C++17	49 / 100	135 ms	176468 KiB

garden

#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 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31