제출 #123380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123380		baluteshih	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	224 ms	32532 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> Gr[150005],cir[300005],nG[300005],ans[2];
int to[300005],in[300005],bln[300005],pl[300005],preans[300005],cnt[300005],ANS[2005];

void dfs1(int u,int d)
{
	if(u&1^1) ++preans[d];
	for(int i:nG[u])
		dfs1(i,d+1);
}

void dfs2(int u,int d,int t)
{
	if(u&1^1) ans[t].pb(d);
	for(int i:nG[u])
		dfs2(i,d+1,t);
}

void doit(int x,int t)
{
	if(!bln[x])
		dfs1(x,0);
	else
	{
		for(int i=0;i<cir[bln[x]].size();++i)
			dfs2(cir[bln[x]][(pl[x]-i+cir[bln[x]].size())%cir[bln[x]].size()],i,t);
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	int tp=0;
	queue<int> q;
	for(int i=0;i<M;++i)
		Gr[R[i][0]].pb(R[i][1]),Gr[R[i][1]].pb(R[i][0]);
	for(int i=0;i<N;++i)
	{
		if(i==Gr[Gr[i][0]][0])
			to[i<<1]=Gr[i][0]<<1|1;
		else
			to[i<<1]=Gr[i][0]<<1;
		if(Gr[i].size()>1)
			if(i==Gr[Gr[i][1]][0])
				to[i<<1|1]=Gr[i][1]<<1|1;
			else
				to[i<<1|1]=Gr[i][1]<<1;
		else
			if(i==Gr[Gr[i][0]][0])
				to[i<<1|1]=Gr[i][0]<<1|1;
			else
				to[i<<1|1]=Gr[i][0]<<1;
		++in[to[i<<1]],++in[to[i<<1|1]];
	}
	for(int i=0;i<2*N;++i)
		if(!in[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(--in[to[u]]==0) q.push(to[u]);
		nG[to[u]].pb(u);
	}
	for(int i=0;i<2*N;++i)
		if(in[i])
		{
			++tp;
			for(int j=i;in[j];j=to[j])
				in[j]=0,bln[j]=tp,pl[j]=cir[tp].size(),cir[tp].pb(j);
		}
	doit(P<<1,0),doit(P<<1|1,1);
	sort(ALL(ans[0])),sort(ALL(ans[1]));
	vector<pii> query;
	for(int i=0;i<Q;++i)
		query.pb(MP(G[i],i));
	sort(ALL(query));
	if(bln[P<<1])
		for(int i=0,j=0;i<Q;++i)
		{
			while(j<ans[0].size()&&ans[0][j]<=query[i].F)
				++cnt[ans[0][j]%cir[bln[P<<1]].size()],++j;
			ANS[query[i].S]+=cnt[query[i].F%cir[bln[P<<1]].size()];
		}
	MEM(cnt,0);
	if(bln[P<<1|1])
		for(int i=0,j=0;i<Q;++i)
		{
			while(j<ans[1].size()&&ans[1][j]<=query[i].F)
				++cnt[ans[1][j]%cir[bln[P<<1|1]].size()],++j;
			ANS[query[i].S]+=cnt[query[i].F%cir[bln[P<<1|1]].size()];
		}
	for(int i=0;i<Q;++i)
		if(G[i]<2*N) ANS[i]+=preans[G[i]];
	for(int i=0;i<Q;++i)
		answer(ANS[i]);
}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void dfs1(int, int)':
garden.cpp:23:6: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  if(u&1^1) ++preans[d];
     ~^~
garden.cpp: In function 'void dfs2(int, int, int)':
garden.cpp:30:6: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  if(u&1^1) ans[t].pb(d);
     ~^~
garden.cpp: In function 'void doit(int, int)':
garden.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<cir[bln[x]].size();++i)
               ~^~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:95:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j<ans[0].size()&&ans[0][j]<=query[i].F)
          ~^~~~~~~~~~~~~~
garden.cpp:103:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j<ans[1].size()&&ans[1][j]<=query[i].F)
          ~^~~~~~~~~~~~~~

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