Submission #834132

#	Time	Username	Problem	Language	Result	Execution time	Memory
834132		ttamx	Tropical Garden (IOI11_garden)	C++14	0 / 100	5 ms	11092 KiB

garden

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

using namespace std;

const int N=150005;
const int M=300005;
const int inf=2e9;

int n,p;
vector<int> padj[N];
vector<pair<int,int>> adj[N][2];
int dp[2][N][2];
int cnt[2][M];
int cyc[2];

void dfs(int t,int u,int s,int d=0){
	dp[t][u][s]=d;
	for(auto [v,w]:adj[u][s]){
		if(v==p&&w==t){
			cyc[t]=d+1;
		}else{
			dfs(t,v,w,d+1);
		}
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n=N,p=P;
	for(int t=0;t<2;t++)for(int i=0;i<n;i++)dp[t][i][0]=dp[t][i][1]=inf;
	for(int i=0;i<M;i++){
		int u=R[i][0],v=R[i][1];
		padj[u].emplace_back(v);
		padj[v].emplace_back(u);
	}
	for(int u=0;u<n;u++){
		for(int s=0;s<2;s++){
			int v=padj[u][min(s,(int)padj[u].size()-1)];
			adj[v][padj[v][0]==u].emplace_back(u,s);
		}
	}
	for(int t=0;t<min(2,(int)padj[p].size());t++){
		dfs(t,p,t);
		for(int i=0;i<n;i++){
			int d=dp[t][i][0];
			if(d==inf)continue;
			cnt[t][d]++;
		}
		if(cyc[t]){
			for(int i=cyc[t]+1;i<=2*n;i++)cnt[t][i]+=cnt[t][i-cyc[i]];
		}
	}
	for(int i=0;i<Q;i++){
		int k=G[i];
		int ans=0;
		for(int t=0;t<2;t++){
			if(k<=2*n)ans+=cnt[t][k];
			else if(cyc[t]){
				int d=k-2*n;
				d=(d+cyc[t]-1)/cyc[t]*cyc[t];
				ans+=cnt[t][k-d];
			}
		}
		answer(ans);
	}
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int, int, int, int)':
garden.cpp:20:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |  for(auto [v,w]:adj[u][s]){
      |           ^

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