Submission #94003

#	Time	Username	Problem	Language	Result	Execution time	Memory
94003		fjzzq2002	Tropical Garden (IOI11_garden)	C++14	100 / 100	524 ms	106704 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
namespace Wrap
{
#define SZ 666666
int n,m,N,p,a[SZ],b[SZ],u[SZ];
int gb(int e,int t)
{return a[e]^b[e]^t;}
vector<int> e[SZ],pre[SZ];
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
struct Sup
{
vector<int> v[SZ];
int GA;
map<int,vector<int> > sb;
void init(int x)
{
	queue<pii> q;
	q.push(pii(x,0));
	while(!q.empty())
	{
		pii w=q.front(); q.pop();
		if(v[w.fi].size()>3) continue;
		v[w.fi].pb(w.se);
		for(auto g:pre[w.fi])
			q.push(pii(g,w.se+1));
	}
	GA=-1;
	for(int i=0;i<N;++i) if(v[i].size()&&i%2==0)
	{
		int G=(v[i].size()>=2)?(v[i][1]-v[i][0]):(1.01e9);
		if(GA==-1) GA=G;
		sb[v[i][0]%G].pb(v[i][0]/G);
	}
	for(auto&u:sb)
		sort(u.se.begin(),u.se.end());
}
int qry(int x)
{
	if(GA==-1) return 0;
	auto&w=sb[x%GA];
	return upper_bound(w.begin(),w.end(),x/GA)-w.begin();
}
}A,B;
}
void count_routes(int N_, int M, int P, int R[][2], int Q, int G[])
{
	using namespace Wrap;
	n=N_,m=M,p=P,N=n*2;
	for(int i=0;i<m;++i)
		a[i]=R[i][0],b[i]=R[i][1],
		e[a[i]].pb(i),e[b[i]].pb(i);
	for(int i=0;i<n;++i)
		for(int j=0;j<2;++j)
		{
			int c=e[i].front();
			if(j&&e[i].size()>1)
				c=e[i][1];
			int w=gb(c,i);
			int d=(e[w].front()==c);
			u[i*2+j]=w*2+d;
			pre[w*2+d].pb(i*2+j);
		}
	A.init(P*2);
	B.init(P*2+1);
	for(int j=0;j<Q;++j)
		answer(A.qry(G[j])+B.qry(G[j]));
}

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