oj.uz

Submission #834141

# Submission time Handle Problem Language Result Execution time Memory
834141 2023-08-22T11:08:35 Z ttamx Tropical Garden (IOI11_garden) C++14
0 / 100
 5 ms 11036 KB 
#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];i<=2*n;i++)cnt[t][i]+=cnt[t][i-cyc[t]];
		}
	}
	for(int i=0;i<Q;i++){
		int k=G[i];
		int ans=0;
		for(int t=0;t<min(2,(int)padj[p].size());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

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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11036 KB Output is correct
2 Correct 5 ms 10964 KB Output is correct
3 Correct 5 ms 10964 KB Output is correct
4 Incorrect 5 ms 10836 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11036 KB Output is correct
2 Correct 5 ms 10964 KB Output is correct
3 Correct 5 ms 10964 KB Output is correct
4 Incorrect 5 ms 10836 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11036 KB Output is correct
2 Correct 5 ms 10964 KB Output is correct
3 Correct 5 ms 10964 KB Output is correct
4 Incorrect 5 ms 10836 KB Output isn't correct
5 Halted 0 ms 0 KB -