Submission #676133

#	Time	Username	Problem	Language	Result	Execution time	Memory
676133		esomer	Tropical Garden (IOI11_garden)	C++17	100 / 100	2473 ms	36308 KiB

garden

#include<bits/stdc++.h>
#include "garden.h"
 
using namespace std;
 
#define ll long long
#define endl "\n"
 
const int MOD = 998244353;
const int maxN = 150000;

pair<int, int> oradj[maxN];
vector<int> adj;
vector<vector<int>> radj;
pair<int, int> ind[maxN]; //First, can take the best, second can't take it.
int rel[2 * maxN];
int dist1[2 * maxN];
int dist2[2 * maxN];
int sz, first, important;

void answer(int x);

bool find_cycle(int x, vector<bool>& vis, vector<bool>& stck){
	if(x == -1) return 0;
	vis[x] = 1;
	stck[x] = 1;
	if(stck[adj[x]]){
		first = adj[x];
		sz = 1;
		return 1;
	}
	if(!vis[adj[x]]){
		bool cyc = find_cycle(adj[x], vis, stck);
		if(cyc){
			sz++;
			if(first == x) return 0;
			else return 1;
		}
	}
	stck[x] = 0;
	if(x == important) sz = -1;
	return 0;
}

void DFS(int x, vector<bool>& vis, int type, int dist){
	if(x == -1) return;
	//~ cout << "X " << x << " dist " << dist << endl;
	if(type == 1) dist1[x] = dist;
	else dist2[x] = dist;
	vis[x] = 1;
	for(int node : radj[x]){
		if(!vis[node]) DFS(node, vis, type, dist + 1);
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	for(int i = 0; i < N; i++) oradj[i] = {-1, -1};
	for(int i = 0; i < M; i++){
		int u = R[i][0]; int v = R[i][1];
		if(oradj[u].first == -1) oradj[u].first = v;
		else if(oradj[u].second == -1) oradj[u].second = v;
		if(oradj[v].first == -1) oradj[v].first = u;
		else if(oradj[v].second == -1) oradj[v].second = u;
	}
	int curr = 0;
	for(int i = 0; i < N; i++){
		if(oradj[i].second != -1){
			ind[i] = {curr, curr + 1};
			rel[curr] = i; rel[curr + 1] = i;
			curr += 2;
		}else{
			ind[i] = {curr, -1}; 
			rel[curr] = i;
			curr++;
		}
	}
	adj.resize(curr); radj.resize(curr);
	for(int i = 0; i < curr; i++){
		int node = rel[i];
		if(ind[node].first == i){
			int go;
			if(oradj[oradj[node].first].first == node){
				if(oradj[oradj[node].first].second == -1) go = ind[oradj[node].first].first;
				else go = ind[oradj[node].first].second;
			}else{
				go = ind[oradj[node].first].first;
			}
			adj[i] = go;
			radj[go].push_back(i);
		}else{
			int go;
			if(oradj[oradj[node].second].first == node){
				if(oradj[oradj[node].second].second == -1) go = ind[oradj[node].second].first;
				else go = ind[oradj[node].second].second;
			}else{
				go = ind[oradj[node].second].first;
			}
			adj[i] = go;
			radj[go].push_back(i);
		}
	}
	//~ for(int i = 0; i < N; i++){
		//~ cout << "I " << i << " ind " << ind[i].first << " " << ind[i].second << endl;
	//~ }
	//~ for(int i = 0; i < curr; i++){
		//~ cout << "I " <<i << " adj " << adj[i] << endl;
	//~ }
	pair<int, int> cycles;
	vector<bool> vis(curr, 0);
	vector<bool> stck(curr, 0);
	sz = -1;
	important = ind[P].first;
	find_cycle(ind[P].first, vis, stck);
	cycles.first = sz; 
	vis.assign(curr, 0); stck.assign(curr, 0);
	sz = -1;
	important = ind[P].second;
	find_cycle(ind[P].second, vis, stck);
	cycles.second = sz;
	vis.assign(curr, 0);
	for(int i = 0; i < curr; i++){
		dist1[i] = -1;
		dist2[i] = -1;
	}
	DFS(ind[P].first, vis, 1, 0);
	vis.assign(curr, 0);
	DFS(ind[P].second, vis, 2, 0);
	//~ cout << "cycles " << cycles.first << " " << cycles.second << endl;
	//~ cout << "Dist1" << endl;
	//~ for(int i = 0; i < curr; i++){
		//~ cout << "I " << i << " " << dist1[i] << endl;
	//~ }
	//~ cout << "Dist2" << endl;
	//~ for(int i = 0; i < curr; i++){
		//~ cout << "I " << i << " " << dist2[i] << endl;
	//~ }
	for(int q = 0; q < Q; q++){
		int k = G[q];
		int ans = 0;
		for(int i = 0; i < N; i++){
			int id = ind[i].first;
			if(dist1[id] != -1 && dist1[id] <= k){
				int left = k - dist1[id];
				if(left == 0 || (cycles.first != -1 && left % cycles.first == 0)) ans++;
			}
			if(dist2[id] != -1 && dist2[id] <= k){
				int left = k - dist2[id];
				if(left == 0 || (cycles.second != -1 && left % cycles.second == 0)) ans++;
			}
		}
		//~ cout << "q " << q << " ans " << ans << " k " << k << endl;
		answer(ans);
	}
}
 
//~ #define MAX_M  1000000
//~ #define MAX_Q  2000

//~ static int N, M, P, Q;
//~ static int R[MAX_M][2];
//~ static int G[MAX_Q];
//~ static int solutions[MAX_Q];
//~ static int answers[MAX_Q];
//~ static int answer_count;

//~ inline 
//~ void my_assert(int e) {if (!e) abort();}
//~ void read_input()
//~ {
  //~ int i;
  //~ my_assert(3==scanf("%d %d %d",&N,&M,&P));
  //~ for(i=0; i<M; i++)
    //~ my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
  //~ my_assert(1==scanf("%d",&Q));
  //~ for(i=0; i<Q; i++)
    //~ my_assert(1==scanf("%d",&G[i]));
  //~ for(i=0; i<Q; i++)
    //~ my_assert(1==scanf("%d",&solutions[i]));
//~ }

//~ void answer(int x)
//~ {
  //~ if(answer_count>=Q) {
    //~ printf("Incorrect.  Too many answers.\n");
    //~ exit(0);
  //~ }
  //~ answers[answer_count] = x;
  //~ answer_count++;
//~ }

//~ int main()
//~ {
  //~ int correct, i;

  //~ read_input();
  //~ answer_count = 0;
  //~ count_routes(N,M,P,R,Q,G);

  //~ if(answer_count!=Q) {
    //~ printf("Incorrect.  Too few answers.\n");
    //~ exit(0);
  //~ }

  //~ correct = 1;
  //~ for(i=0; i<Q; i++)
    //~ if(answers[i]!=solutions[i])
      //~ correct = 0;
  //~ if(correct)
    //~ printf("Correct.\n");
  //~ else {
    //~ printf("Incorrect.\n");
    //~ printf("Expected: ");
    //~ for(i=0; i<Q; i++)
      //~ printf("%d ",solutions[i]);
    //~ printf("\nReturned: ");
    //~ for(i=0; i<Q; i++)
      //~ printf("%d ",answers[i]);
  //~ }
  //~ return 0;
//~ }

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