제출 #751200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751200		minhcool	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	2622 ms	72992 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define ll long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
/*
Algo: We have 2n nodes (i, 0/1 - is last node the largest)
Just for lmao
*/
 
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;
 
const ll N = 3e5 + 5;
 
const ll oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
ll n, m, p, q;
vector<ll> Adj[N]; 
 
// cycles that node u can get
vector<ii> cyc[N][2];
 
//map<ii, ll> mp;
 
ii nxt[N][2];
 
ll mn_dist[N][2];
 
vector<ii> Adj2[N][2];
 
iiii savee[N];
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n = N, m = M, p = P;
	for(ll i = 0; i < m; i++){
		Adj[R[i][0]].pb(R[i][1]);
		Adj[R[i][1]].pb(R[i][0]);
		//mp[{min(R[i][0], R[i][1]), m}
	}
	for(ll i = 0; i < n; i++){
		// last trail is the best in all trails from i -> need to choose second if there is one
		if(Adj[i].size() >= 2) nxt[i][1] = {Adj[i][1], (Adj[Adj[i][1]][0] == i)};
		else nxt[i][1] = {Adj[i][0], (Adj[Adj[i][0]][0] == i)};
		nxt[i][0] = {Adj[i][0], (Adj[Adj[i][0]][0] == i)};
	}
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < 2; j++){
			Adj2[nxt[i][j].fi][nxt[i][j].se].pb({i, j});
		}
	}
	// finding the cycle for (p, 0)
	ii itr = {p, 0};
	ll len = 0;
	while((!len || itr != make_pair(p, 0LL)) && len <= 2 * n){
		len++;
		itr = nxt[itr.fi][itr.se];
	}
	if(len > 2 * n) len = oo;
	for(ll i = 0; i < n; i++) mn_dist[i][0] = mn_dist[i][1] = oo;
	mn_dist[p][0] = 0;
	queue<ii> bfs;
	bfs.push({p, 0});
	while(!bfs.empty()){
		ii u = bfs.front();
		bfs.pop();
		for(auto it : Adj2[u.fi][u.se]){
			if(mn_dist[it.fi][it.se] != oo) continue;
			mn_dist[it.fi][it.se] = mn_dist[u.fi][u.se] + 1;
			bfs.push(it);
		}
	}
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < 2; j++){
			if(mn_dist[i][j] == oo) continue;
			cyc[i][j].pb({mn_dist[i][j], len});	
		}
	}
	itr = {p, 1};
	len = 0;
	while((!len || itr != make_pair(p, 1LL)) && len <= 2 * n){
		len++;
		itr = nxt[itr.fi][itr.se];
	}
	if(len > 2 * n) len = oo;
	for(ll i = 0; i < n; i++) mn_dist[i][0] = mn_dist[i][1] = oo;
	mn_dist[p][1] = 0;
	//queue<ii> bfs;
	bfs.push({p, 1});
	//cout << "OKAY\n";
	while(!bfs.empty()){
		ii u = bfs.front();
		bfs.pop();
		for(auto it : Adj2[u.fi][u.se]){
			if(mn_dist[it.fi][it.se] != oo) continue;
			mn_dist[it.fi][it.se] = mn_dist[u.fi][u.se] + 1;
			bfs.push(it);
		}
	}
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < 2; j++){
			if(mn_dist[i][j] == oo) continue;
			cyc[i][j].pb({mn_dist[i][j], len});	
			//cout << i << " " << j << " " << mn_dist[i][j] << " " << len << "\n";
		}
	}
//	exit(0);
    for(ll i = 0; i < n; i++){
    	ii temp = {Adj[i][0], (Adj[Adj[i][0]][0] == i)};
        savee[i] = {{-1, -1}, {-1, -1}};
        for(auto it : cyc[temp.fi][temp.se]){
        	if(savee[i].fi.fi < 0) savee[i].fi = it;
          else savee[i].se = it;
        }
    }
	for(ll i = 0; i < Q; i++){
		ll tol = 0;
		G[i]--;
		for(ll j = 0; j < n; j++){
			//cout << temp.fi << " " << temp.se << "\n";
			//cout << j << " " << Adj[j][0] << "\n";
			//continue;
			bool ck = 0;
			if(savee[j].fi.fi >= 0){
                ll diff = G[i] - savee[j].fi.fi;
            	ck = (diff >= 0 && !(diff % savee[j].fi.se));
                if(!ck && savee[j].se.fi >= 0){
                  ll diff = G[i] - savee[j].se.fi;
                  ck = (diff >= 0 && !(diff % savee[j].se.se));
                }
            }
			tol += ck;
		}
		//cout << i << " " << tol << "\n";
		answer(tol);
	//if(n >= 100000 && Q > 1) exit(0);
	}
}

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