oj.uz

답안 #94001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94001 2019-01-14T14:10:10 Z fjzzq2002 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 66 ms 63404 KB 
#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(w.se>100) continue;
//		if(v[w.fi].size()>2) 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;
//		if(GA!=G) throw "GG";
//		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)
{
	int ans=0;
	for(int i=0;i<N;i+=2)
		ans+=binary_search(v[i].begin(),v[i].end(),x);
	return ans;
//	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]));
}
//try sub1

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 63152 KB Output is correct
2 Correct 60 ms 63156 KB Output is correct
3 Correct 60 ms 63192 KB Output is correct
4 Correct 60 ms 63024 KB Output is correct
5 Correct 59 ms 62964 KB Output is correct
6 Correct 60 ms 63136 KB Output is correct
7 Correct 61 ms 63024 KB Output is correct
8 Correct 62 ms 63252 KB Output is correct
9 Correct 66 ms 63404 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 63152 KB Output is correct
2 Correct 60 ms 63156 KB Output is correct
3 Correct 60 ms 63192 KB Output is correct
4 Correct 60 ms 63024 KB Output is correct
5 Correct 59 ms 62964 KB Output is correct
6 Correct 60 ms 63136 KB Output is correct
7 Correct 61 ms 63024 KB Output is correct
8 Correct 62 ms 63252 KB Output is correct
9 Correct 66 ms 63404 KB Output is correct
10 Incorrect 61 ms 63068 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 63152 KB Output is correct
2 Correct 60 ms 63156 KB Output is correct
3 Correct 60 ms 63192 KB Output is correct
4 Correct 60 ms 63024 KB Output is correct
5 Correct 59 ms 62964 KB Output is correct
6 Correct 60 ms 63136 KB Output is correct
7 Correct 61 ms 63024 KB Output is correct
8 Correct 62 ms 63252 KB Output is correct
9 Correct 66 ms 63404 KB Output is correct
10 Incorrect 61 ms 63068 KB Output isn't correct
11 Halted 0 ms 0 KB -