oj.uz

Submission #537854

# Submission time Handle Problem Language Result Execution time Memory
537854 2022-03-15T17:25:58 Z myrcella Tropical Garden (IOI11_garden) C++17
100 / 100
 207 ms 42496 KB 
#include "garden.h"
#include "gardenlib.h"

#include<bits/stdc++.h>
using namespace std;
/*
#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;


void read_input()
{
  int i;
  scanf("%d %d %d",&N,&M,&P);
  for(i=0; i<M; i++)
   scanf("%d %d",&R[i][0],&R[i][1]);
  scanf("%d",&Q);
  for(i=0; i<Q; i++)
    scanf("%d",&G[i]);
  for(i=0; i<Q; i++)
    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++;
}

*/

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 4e5;

int best[maxn],best2[maxn];
vector <int> edge[maxn][2];
int len[2]={0,0};
bool vis[maxn][2];
int dis[maxn][2][2];
int ans[maxn][2];
pq <pii,vector<pii>,greater<pii> > q;
int p;

void dfs(int u,int rk,int cnt,int id) {
	if (vis[u][rk]) return;
	vis[u][rk]=true;
	int v = best[u];
	if (rk==1 and best2[u]!=-1) v = best2[u];
  	if (u==p and cnt>1 and (id==0 and best[u]==v or id==1 and best2[u]==v)) {
      	len[id]=cnt;
      	return;
    }     
	dfs(v,(best[v]==u),cnt+1,id);
}

void dijkstra(int id) {
	while (!q.empty()) {
		int uu = q.top().se;
		int d = q.top().fi;
		int u = uu%maxn,a=uu/maxn;
		q.pop();
		if (dis[u][a][id]!=d) continue;
		if (a==0) {
			ans[d][id]++;
			for (int v:edge[u][0]) if (dis[v][0][id]>d+1) {
				if (best[u]==v and best2[u]!=-1) continue;
				dis[v][0][id]=d+1;
				q.push(MP(d+1,v));
			}
			for (int v:edge[u][1]) if (dis[v][1][id]>d+1) {
				if (best[u]==v and best2[u]!=-1) continue;
				dis[v][1][id]=d+1;
				q.push(MP(d+1,v+maxn));
			}
		}
		else {
			if (best[best[u]]==u&&dis[best[u]][0][id]>d+1) {
				dis[best[u]][0][id]=d+1;
				q.push(MP(d+1,best[u]));
			}
			else if (best2[best[u]]==u&&dis[best[u]][1][id]>d+1) {
				dis[best[u]][1][id]=d+1;
				q.push(MP(d+1,best[u]+maxn));
			}
		}
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	p = P;
	memset(best,-1,sizeof(best));
	memset(best2,-1,sizeof(best2));
	memset(dis,inf,sizeof(dis));
	memset(ans,0,sizeof(ans));
	rep(i,0,M) {
		if (best[R[i][0]]==-1) best[R[i][0]] = R[i][1],edge[R[i][1]][0].pb(R[i][0]);
		else if (best2[R[i][0]]==-1) best2[R[i][0]] = R[i][1],edge[R[i][1]][1].pb(R[i][0]);
		if (best[R[i][1]]==-1) best[R[i][1]] = R[i][0],edge[R[i][0]][0].pb(R[i][1]);
		else if (best2[R[i][1]]==-1) best2[R[i][1]] = R[i][0],edge[R[i][0]][1].pb(R[i][1]);
	}
	
	memset(vis,0,sizeof(vis));
	dfs(best[p],best[best[p]]==p,1,0);
	dis[p][0][0] = 0;
	q.push(MP(0,p));
	dijkstra(0);
	
	if(best2[p]!=-1) {
	
		memset(vis,0,sizeof(vis));
		dfs(best2[p],best[best2[p]]==p,1,1);
		dis[p][1][1] = 0;
		q.push(MP(0,maxn+p));
		dijkstra(1);
	}
	
	rep(i,0,Q) {
		int res = 0;
		rep(j,0,2) {
			if (len[j]==0 and G[i]<maxn) res+=ans[G[i]][j];
			else if (len[j]>0) for (int k=G[i]%len[j];k<maxn&&k<=G[i];k+=len[j]) res+=ans[k][j];
		}
		answer(res);
	}
}
/*
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;
}
*/

Compilation message

garden.cpp: In function 'void dfs(int, int, int, int)':
garden.cpp:78:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   78 |    if (u==p and cnt>1 and (id==0 and best[u]==v or id==1 and best2[u]==v)) {
      |                            ~~~~~~^~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32468 KB Output is correct
2 Correct 17 ms 32408 KB Output is correct
3 Correct 19 ms 32488 KB Output is correct
4 Correct 17 ms 32340 KB Output is correct
5 Correct 16 ms 32340 KB Output is correct
6 Correct 17 ms 32436 KB Output is correct
7 Correct 16 ms 32340 KB Output is correct
8 Correct 17 ms 32420 KB Output is correct
9 Correct 18 ms 32468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32468 KB Output is correct
2 Correct 17 ms 32408 KB Output is correct
3 Correct 19 ms 32488 KB Output is correct
4 Correct 17 ms 32340 KB Output is correct
5 Correct 16 ms 32340 KB Output is correct
6 Correct 17 ms 32436 KB Output is correct
7 Correct 16 ms 32340 KB Output is correct
8 Correct 17 ms 32420 KB Output is correct
9 Correct 18 ms 32468 KB Output is correct
10 Correct 17 ms 32340 KB Output is correct
11 Correct 24 ms 33752 KB Output is correct
12 Correct 34 ms 34764 KB Output is correct
13 Correct 53 ms 39372 KB Output is correct
14 Correct 81 ms 39664 KB Output is correct
15 Correct 141 ms 39948 KB Output is correct
16 Correct 96 ms 38376 KB Output is correct
17 Correct 80 ms 38128 KB Output is correct
18 Correct 31 ms 34632 KB Output is correct
19 Correct 69 ms 39628 KB Output is correct
20 Correct 110 ms 40012 KB Output is correct
21 Correct 85 ms 38280 KB Output is correct
22 Correct 91 ms 37956 KB Output is correct
23 Correct 78 ms 40144 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32468 KB Output is correct
2 Correct 17 ms 32408 KB Output is correct
3 Correct 19 ms 32488 KB Output is correct
4 Correct 17 ms 32340 KB Output is correct
5 Correct 16 ms 32340 KB Output is correct
6 Correct 17 ms 32436 KB Output is correct
7 Correct 16 ms 32340 KB Output is correct
8 Correct 17 ms 32420 KB Output is correct
9 Correct 18 ms 32468 KB Output is correct
10 Correct 17 ms 32340 KB Output is correct
11 Correct 24 ms 33752 KB Output is correct
12 Correct 34 ms 34764 KB Output is correct
13 Correct 53 ms 39372 KB Output is correct
14 Correct 81 ms 39664 KB Output is correct
15 Correct 141 ms 39948 KB Output is correct
16 Correct 96 ms 38376 KB Output is correct
17 Correct 80 ms 38128 KB Output is correct
18 Correct 31 ms 34632 KB Output is correct
19 Correct 69 ms 39628 KB Output is correct
20 Correct 110 ms 40012 KB Output is correct
21 Correct 85 ms 38280 KB Output is correct
22 Correct 91 ms 37956 KB Output is correct
23 Correct 78 ms 40144 KB Output is correct
24 Correct 18 ms 32340 KB Output is correct
25 Correct 24 ms 33748 KB Output is correct
26 Correct 40 ms 34640 KB Output is correct
27 Correct 55 ms 39324 KB Output is correct
28 Correct 207 ms 39584 KB Output is correct
29 Correct 172 ms 40212 KB Output is correct
30 Correct 82 ms 38296 KB Output is correct
31 Correct 104 ms 38208 KB Output is correct
32 Correct 34 ms 34636 KB Output is correct
33 Correct 189 ms 39628 KB Output is correct
34 Correct 187 ms 40000 KB Output is correct
35 Correct 102 ms 38344 KB Output is correct
36 Correct 119 ms 38132 KB Output is correct
37 Correct 75 ms 40084 KB Output is correct
38 Correct 115 ms 42496 KB Output is correct