Submission #717865

#	Time	Username	Problem	Language	Result	Execution time	Memory
717865		TheSahib	Tropical Garden (IOI11_garden)	C++17	0 / 100	6 ms	9684 KiB

garden

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

#define ll long long
#define pii pair<int, int>
#define oo 1e9

using namespace std;

bool comp(pii a, pii b){
    return a.second < b.second;
}

const int MAX = 3e5 + 5;

int n, m, f;
vector<pii> g[MAX];
int tmpG[MAX];

int revG[MAX];
pii dist[MAX];

int dfs(int node, int d){
    if(revG[node] != f && dist[revG[node]].first < d + 1) return 0;
    dist[node].first = min(dist[node].first, d);
    
    int c = 0;
    if(revG[node] == f){
        c = d + 1;
    }
    else{
        c = dfs(revG[node], d + 1);
    }

    if(c){
        dist[node].second = c - dist[node].first;
    }
    return c;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    fill(dist, dist + MAX, make_pair(oo, oo));
    f = P;
    n = N;
    m = M;

    for (int i = 0; i < m; i++)
    {
        g[R[i][0]].push_back({R[i][1], i});
        g[R[i][1]].push_back({R[i][0], i});
    }
    for (int i = 0; i < n; i++)
    {
        sort(g[i].begin(), g[i].end(), comp);
    }
    for (int i = 0; i < n; i++)
    {
        if(g[i][0].second == g[g[i][0].first][0].second){
            tmpG[i] = g[i][0].first + n;
        }
        else{
            tmpG[i] = g[i][0].first;
        }
        if(g[i].size() >= 2){
            if(g[i][1].second == g[g[i][1].first][0].second){
                tmpG[i + n] = g[i][1].first + n;
            }
            else{
                tmpG[i + n] = g[i][1].first;
            }
        }
        if(g[i].size() == 1){
            tmpG[i + n] = tmpG[i];
        }
    }
    for (int i = 0; i < (n << 1); i++)
    {
        revG[tmpG[i]] = i;
    }
    
    dfs(f, 0);
    dfs(f + n, 0);
    for (int j = 0; j < Q; j++)
    {
        int ans = 0;
        for (int i = 0; i < (n << 1); i++)
        {
            if(dist[i].first == oo) continue;
            if(dist[i].second == oo) ans += (dist[i].first == G[j]);
            else if(G[j] - dist[i].first >= 0) ans += ((G[j] - dist[i].first) % dist[i].second) == 0;
        }
        answer(ans);
    }
    
}

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