Submission #1092981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092981		Aviansh	Tropical Garden (IOI11_garden)	C++17	0 / 100	1 ms	604 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

void dfs(int st, int dep, vector<int>(&g)[], int f[], int t, int n){
    f[st]=dep;
    for(int i : g[st]){
        if(i==t){
            f[t]=dep+1;
            continue;
        }
        if(i==st+n||i==st-n){
            dfs(i,dep,g,f,t, n);
            continue;
        }
        dfs(i,dep+1,g,f,t, n);
    }
}

void count_routes(int n, int m, int t, int edges[][2], int q, int G[])
{
    vector<int>g[2*n];
    int cn[n];
    fill(cn,cn+n,0);
    for(int i = 0;i<m;i++){
        int u1=edges[i][0];
        int v1=edges[i][1];
        if(cn[u1]>cn[v1]){
            swap(u1,v1);
        }
        int u2 = u1+n;
        int v2 = v1+n;
        if(cn[u1]==0&&cn[v1]==0){
            g[v2].push_back(u1);
            g[u2].push_back(v1);
        }
        else if(cn[u1]==0&&cn[v1]==1){
            g[v1].push_back(u1);
            g[u2].push_back(v2);
        }
        else if(cn[u1]==0&&cn[v1]>1){
            g[v1].push_back(u1);
        }
        else if(cn[u1]==1&&cn[v1]==1){
            g[v1].push_back(u2);
            g[u1].push_back(v2);
        }
        else if(cn[u1]==1&&cn[v1]>1){
            g[v1].push_back(u2);
        }
        cn[u1]++;
        cn[v1]++;
    }
    for(int i = 0;i<n;i++){
        if(cn[i]==1){
            g[i].push_back(i+n);
        }
    }
    int f1[2*n];
    fill(f1,f1+2*n,-1);
    dfs(t,0,g,f1,t, n);
    int f2[2*n];
    fill(f2,f2+2*n,-1);
    dfs(t+n,0,g,f2,t+n, n);
    auto t1 = [&] (int u, int D) -> bool{
        if(f1[u]==-1) return 0;
        if(f1[u]==D) return 1;
        if(f1[u]>D) return 0;
        return f1[t] && (D-f1[u])%f1[t]==0;
    };

    auto t2 = [&] (int u, int D) -> bool{
        if(f2[u]==-1) return 0;
        if(f2[u]==D) return 1;
        if(f2[u]>D) return 0;
        return f2[t+n] && (D-f2[u])%f2[t+n]==0;
    };
    for(int i = 0;i<q;i++){
        int ans = 0;
        for(int j = 0;j<n;j++){
            if(t1(j,G[i])||t2(j,G[i])){
                ans++;
            }
        }
        answer(ans);
    }
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31