Submission #269134

#	Time	Username	Problem	Language	Result	Execution time	Memory
269134		Autoratch	Tropical Garden (IOI11_garden)	C++14	49 / 100	16 ms	14976 KiB

garden

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

const int N = 2e5;

vector<pair<int,int> > adj[N];
pair<int,int> ed[N << 1];
vector<int> res[N << 1];
queue<tuple<int,int,int,int> > q;

void bfs()
{
    while(!q.empty())
    {
        auto [u,p,id,cnt] = q.front();
        q.pop();
//        if(res[id].size()>=5) continue;
        if(cnt>100) continue;
        if(u!=p and p==adj[u][0].second) res[id].push_back(cnt);
        if(id==-1 or adj[u][0].second==p)
        { 
            for(auto [w,v] : adj[u]) if(v!=p or adj[u].size()==1) q.push({v,u,w,cnt+1}); 
        }
        else if(adj[u][1].second==p)
        { 
            auto [w,v] = adj[u][0]; if(v!=p) q.push({v,u,w,cnt+1}); 
        }
    }
}

void dfs(int u,int p,int id,int cnt)
{
    q.push({u,p,id,cnt});
    bfs();
    return;
    if(res[id].size()>=5) return;
    res[id].push_back(cnt);
    if(id==-1 or adj[u][0].second==p)
    {
        for(auto [w,v] : adj[u]) if(v!=p or adj[u].size()==1) dfs(v,u,w,cnt+1);
    }
    else if(adj[u][1].second==p) 
    {
        auto [w,v] = adj[u][0];
        if(v!=p) dfs(v,u,w,cnt+1);
    }
}

void count_routes(int n,int m,int p,int r[][2],int q,int g[])
{
    for(int i = 0,j = 0;i < m;i++)
    {
        int a = r[i][0],b = r[i][1];
        ed[j] = {a,b};
        adj[a].push_back({j++,b});
        ed[j] = {b,a};
        adj[b].push_back({j++,a});
    }
    dfs(p,p,-1,0);
    for(int i = 0;i < q;i++)
    {
        int ans = 0;
        for(int j = 0;j < m*2;j++) for(int x : res[j]) if(x==g[i]) ans++;
        /*
        {
            if(res[j].size()>0 and res[j][0]==g[i]) ans++;
            else if(res[j].size()>2 and (g[i]-res[j][1])%(res[j][2]-res[j][1])==0) ans++;
        }
        */
        answer(ans);
    }
    return;
    for(int i = 0;i < m*2;i++) 
    {
        cout << ed[i].first << ' ' << ed[i].second << endl;
        for(int x : res[i]) cout << x << ' ' ;
        cout << endl;
    }
    
}

Compilation message (stderr)

garden.cpp: In function 'void bfs()':
garden.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |         auto [u,p,id,cnt] = q.front();
      |              ^
garden.cpp:24:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |             for(auto [w,v] : adj[u]) if(v!=p or adj[u].size()==1) q.push({v,u,w,cnt+1});
      |                      ^
garden.cpp:28:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |             auto [w,v] = adj[u][0]; if(v!=p) q.push({v,u,w,cnt+1});
      |                  ^
garden.cpp: In function 'void dfs(int, int, int, int)':
garden.cpp:42:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for(auto [w,v] : adj[u]) if(v!=p or adj[u].size()==1) dfs(v,u,w,cnt+1);
      |                  ^
garden.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         auto [w,v] = adj[u][0];
      |              ^

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