Submission #1051735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051735		AndreasK	Tropical Garden (IOI11_garden)	C++14	49 / 100	5096 ms	4188 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

#define designed ios_base::sync_with_stdio(0);
#define by cin.tie(0);
#define AndreasK cout.tie(0);
//#define int long long
#define ii pair <int,int>
#define vi vector <int>
#define iii pair <int,ii>
#define vii vector <ii>
#define vc vector <char>
#define vb vector <bool>

vector <vii> graph;
int ans;
void dfs(int curr,int prev,int have,int should){
if (have==should)
    ans=curr;
else if (graph[curr].size()==1){
    dfs(graph[curr][0].first,curr,have+1,should);
}
else{
    int mx=-1;
    int mxn=0;
    for (ii nxt:graph[curr]){
        if (nxt.first!=prev){
        if (nxt.second>mx){
            mxn=nxt.first;
            mx=nxt.second;
        }
        }
    }
    dfs(mxn,curr,have+1,should);
}
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
graph.assign(n,vii());
for (int c=0;c<m;c++){
    graph[r[c][0]].push_back({r[c][1],m-c});
    graph[r[c][1]].push_back({r[c][0],m-c});
}
for (int r=0;r<q;r++){
    int ttl=0;
    for (int c=0;c<n;c++){
        dfs(c,c,0,g[r]);
        if (ans==p)
            ttl++;
    }
    answer(ttl);
}
}

/*int32_t main(){
    designed by AndreasK
    freopen("akinput.txt","r",stdin);
    int n,m,p;
    cin>>n>>m>>p;
    int r[m][2];
    for (int c=0;c<m;c++)
        cin>>r[c][0]>>r[c][1];
    int q;
    cin>>q;
    int g[q];
    for (auto &c:g)
        cin>>c;
    count_routes(n,m,p,r,q,g);
return 0;}*/

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