Submission #800412

#	Time	Username	Problem	Language	Result	Execution time	Memory
800412		Antekb	Tropical Garden (IOI11_garden)	C++17	49 / 100	77 ms	22716 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>;
using namespace std;
#define st first
#define nd second
#define pb push_back
using pii = pair<int, int>;
using vi = vector<int>;

void count_routes(int n, int m, int p, int edg[][2], int q, int QQ[])
{
	vector<pii> E[n][2];
	int naj[n][2], co[n][2], dist[n][2], typ[n][2];
	for(int i=0; i<n; i++){
		naj[i][0]=naj[i][1]=1e9+5;
	}
	for(int i=m-1; i>=0; i--){
		naj[edg[i][0]][0]=i;
		co[edg[i][0]][0]=edg[i][1];
		naj[edg[i][1]][0]=i;
		co[edg[i][1]][0]=edg[i][0];
	}
	for(int i=m-1; i>=0; i--){
		if(naj[edg[i][0]][0]!=i){
			naj[edg[i][0]][1]=i;
			co[edg[i][0]][1]=edg[i][1];
		}
		if(naj[edg[i][1]][0]!=i){
			naj[edg[i][1]][1]=i;
			co[edg[i][1]][1]=edg[i][0];
		}
	}
	for(int i=0; i<n; i++){
		dist[i][0]=dist[i][1]=1e9+5;
		if(naj[i][1]==1e9+5){
			naj[i][1]=naj[i][0];
			co[i][1]=co[i][0];
		}
		//cerr<<i<<" "<<naj[i][0]<<" "<<co[i][0]<<" "<<naj[i][1]<<" "<<co[i][1]<<"\n";
		E[co[i][0]][(naj[i][0]==naj[co[i][0]][0])].pb({i, 0});
		E[co[i][1]][(naj[i][1]==naj[co[i][1]][0])].pb({i, 1});
	}
	vector<pii> V;
	for(int i=0; i<n; i++){
		if(co[i][0]==p){
			V.pb({i, 0});
			dist[i][0]=1;
			typ[i][0]=(naj[i][0]==naj[p][0]);
		}
		if(co[i][1]==p){
			V.pb({i, 1});
			dist[i][1]=1;
			typ[i][1]=(naj[i][1]==naj[p][0]);
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<2; j++){
			//cerr<<i<<" "<<j<<": ";
			for(pii e:E[i][j]){
				//cerr<<"{"<<e.st<<", "<<e.nd<<"} ";
			}
			//cerr<<"\n";
		}
	}
	for(int i=0; i<V.size(); i++){
		//cerr<<V[i].st<<" "<<V[i].nd<<"\n";
		for(pii e:E[V[i].st][V[i].nd]){
			if(dist[e.st][e.nd]!=1e9+5)continue;
			V.pb(e);
			typ[e.st][e.nd]=typ[V[i].st][V[i].nd];
			dist[e.st][e.nd]=dist[V[i].st][V[i].nd]+1;
		}
	}
	vector<vector<int> > cykle;
	vector<pair<int, int> > eve;
	vector<int> eve2;
	for(int i=0; i<n; i++){
		for(int j=0; j<1; j++){
			if(dist[i][j]!=1e9+5){
				//cerr<<i<<" "<<j<<" "<<dist[i][j]<<" "<<typ[i][j]<<": ";
				if(dist[p][typ[i][j]]==1e9+5){
					eve2.pb(dist[i][j]);
					//cerr<<dist[i][j]<<"\n";
				}
				else{
					if(typ[p][typ[i][j]]==typ[i][j]){
						eve.pb({dist[i][j], dist[p][typ[i][j]]});
						//cerr<<"{"<<dist[i][j]<<", "<<dist[p][typ[i][j]]<<"}\n";
					}
					else{
						if(dist[p][typ[i][j]^1]==1e9+5){
							eve2.pb(dist[i][j]);
							eve2.pb(dist[i][j]+dist[p][typ[i][j]]);
							//cerr<<dist[i][j]<<" "<<dist[i][j]+dist[p][typ[i][j]]<<"\n";
						}
						else{
							eve.pb({dist[i][j], dist[p][0]+dist[p][1]});
							eve.pb({dist[i][j]+dist[p][typ[i][j]], dist[p][0]+dist[p][1]});
							//cerr<<"{"<<dist[i][j]<<", "<<dist[p][typ[i][j]]<<"}";
							//cerr<<"{"<<dist[i][j]+dist[p][typ[i][j]]<<", "<<dist[p][0]+dist[p][1]<<"}\n";
						}
					}
				}
			}
		}
	}
	sort(eve.begin(), eve.end());
	sort(eve2.begin(), eve2.end());
	reverse(eve.begin(), eve.end());
	reverse(eve2.begin(), eve2.end());
	vector<pii> Q(q);
	vector<int> ans(q);
	for(int i=0; i<q; i++){
		Q[i].st=QQ[i];
		Q[i].nd=i;
	}
	sort(Q.begin(), Q.end());
	for(pii ii:Q){
		int i=ii.st, qq=ii.nd;
		while(eve2.size() && eve2.back()<i)eve2.pop_back();
		while(eve2.size() && eve2.back()==i)eve2.pop_back(), ans[qq]++;
		while(eve.size() && eve.back().st<=i){
			if(cykle.size()>0 && cykle[0].size()==eve.back().nd){
				cykle[0][eve.back().st%eve.back().nd]++;
			}
			else if(cykle.size()>1 && cykle[1].size()==eve.back().nd){
				cykle[1][eve.back().st%eve.back().nd]++;
			}
			else{
				cykle.pb(vi(eve.back().nd));
				cykle.back()[eve.back().st%eve.back().nd]++;
			}
			eve.pop_back();
		}
		if(cykle.size()>0)ans[qq]+=cykle[0][i%cykle[0].size()];
		if(cykle.size()>1)ans[qq]+=cykle[1][i%cykle[1].size()];
	}
	for(int i=0; i<q; i++){
		answer(ans[i]);
	}
}

Compilation message (stderr)

garden.cpp:3:24: warning: extra tokens at end of #include directive
    3 | #include<bits/stdc++.h>;
      |                        ^
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:60:12: warning: variable 'e' set but not used [-Wunused-but-set-variable]
   60 |    for(pii e:E[i][j]){
      |            ^
garden.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
garden.cpp:124:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  124 |    if(cykle.size()>0 && cykle[0].size()==eve.back().nd){
      |                                        ^
garden.cpp:127:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |    else if(cykle.size()>1 && cykle[1].size()==eve.back().nd){
      |                                             ^

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