oj.uz

Submission #218912

# Submission time Handle Problem Language Result Execution time Memory
218912 2020-04-03T06:12:46 Z FieryPhoenix Tropical Garden (IOI11_garden) C++11
100 / 100
 2802 ms 41720 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
#define f first
#define s second

int N,M,P;
int x[150001],y[150001];
vector<pair<int,int>>adj[150001];
vector<int>adj2[300001];
int dis[300001][2],size[2];
int minEdge[300001];

void dfs(int node, int source, bool b){
  for (int x:adj2[node]){
    if (x==source){
      assert(size[b]==0);
      size[b]=dis[node][b]+1;
      continue;
    }
    if (dis[x][b]==0){
      dis[x][b]=dis[node][b]+1;
      dfs(x,source,b);
    }
  }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
  for (int i=0;i<M;i++){
    x[i]=R[i][0];
    y[i]=R[i][1];
    adj[x[i]].push_back({i,y[i]});
    adj[y[i]].push_back({i,x[i]});
  }
  for (int i=0;i<N;i++){
    sort(adj[i].begin(),adj[i].end());
    minEdge[i]=adj[i][0].first;
  }
  for (int i=0;i<N;i++){
    if ((int)adj[i].size()==1){
      adj2[adj[i][0].s+N*(adj[i][0].f==minEdge[adj[i][0].s])].push_back(i);
      adj2[adj[i][0].s+N*(adj[i][0].f==minEdge[adj[i][0].s])].push_back(i+N);
    }
    else{
      adj2[adj[i][0].s+N*(adj[i][0].f==minEdge[adj[i][0].s])].push_back(i);
      adj2[adj[i][1].s+N*(adj[i][1].f==minEdge[adj[i][1].s])].push_back(i+N);
    }
  }
  dfs(P,P,0);
  dfs(P+N,P+N,1);
  for (int i=0;i<Q;i++){
    int K=G[i];
    int ans=0;
    for (int j=0;j<N;j++){
      bool good=false;
      for (int k=0;k<2;k++){
	if (dis[j][k]!=0){
	  if (size[k]==0){
	    if (dis[j][k]==K)
	      good=true;
	  }
	  else{
	    if (K-dis[j][k]>=0 && size[k]!=0 && (K-dis[j][k])%size[k]==0)
	      good=true;
	  }
	}
	else if (j==P && size[k]!=0 && K%size[k]==0)
	  good=true;

      }
      ans+=good;
    }
    answer(ans);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11136 KB Output is correct
2 Correct 12 ms 11008 KB Output is correct
3 Correct 12 ms 11008 KB Output is correct
4 Correct 11 ms 10880 KB Output is correct
5 Correct 11 ms 10880 KB Output is correct
6 Correct 12 ms 11188 KB Output is correct
7 Correct 11 ms 11008 KB Output is correct
8 Correct 11 ms 11008 KB Output is correct
9 Correct 14 ms 11392 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11136 KB Output is correct
2 Correct 12 ms 11008 KB Output is correct
3 Correct 12 ms 11008 KB Output is correct
4 Correct 11 ms 10880 KB Output is correct
5 Correct 11 ms 10880 KB Output is correct
6 Correct 12 ms 11188 KB Output is correct
7 Correct 11 ms 11008 KB Output is correct
8 Correct 11 ms 11008 KB Output is correct
9 Correct 14 ms 11392 KB Output is correct
10 Correct 11 ms 11008 KB Output is correct
11 Correct 23 ms 13696 KB Output is correct
12 Correct 41 ms 15992 KB Output is correct
13 Correct 65 ms 33656 KB Output is correct
14 Correct 151 ms 27168 KB Output is correct
15 Correct 164 ms 27640 KB Output is correct
16 Correct 132 ms 24184 KB Output is correct
17 Correct 119 ms 23036 KB Output is correct
18 Correct 44 ms 16056 KB Output is correct
19 Correct 145 ms 27128 KB Output is correct
20 Correct 166 ms 27640 KB Output is correct
21 Correct 127 ms 24060 KB Output is correct
22 Correct 116 ms 23032 KB Output is correct
23 Correct 140 ms 28536 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11136 KB Output is correct
2 Correct 12 ms 11008 KB Output is correct
3 Correct 12 ms 11008 KB Output is correct
4 Correct 11 ms 10880 KB Output is correct
5 Correct 11 ms 10880 KB Output is correct
6 Correct 12 ms 11188 KB Output is correct
7 Correct 11 ms 11008 KB Output is correct
8 Correct 11 ms 11008 KB Output is correct
9 Correct 14 ms 11392 KB Output is correct
10 Correct 11 ms 11008 KB Output is correct
11 Correct 23 ms 13696 KB Output is correct
12 Correct 41 ms 15992 KB Output is correct
13 Correct 65 ms 33656 KB Output is correct
14 Correct 151 ms 27168 KB Output is correct
15 Correct 164 ms 27640 KB Output is correct
16 Correct 132 ms 24184 KB Output is correct
17 Correct 119 ms 23036 KB Output is correct
18 Correct 44 ms 16056 KB Output is correct
19 Correct 145 ms 27128 KB Output is correct
20 Correct 166 ms 27640 KB Output is correct
21 Correct 127 ms 24060 KB Output is correct
22 Correct 116 ms 23032 KB Output is correct
23 Correct 140 ms 28536 KB Output is correct
24 Correct 12 ms 11008 KB Output is correct
25 Correct 157 ms 13688 KB Output is correct
26 Correct 234 ms 16120 KB Output is correct
27 Correct 2548 ms 33668 KB Output is correct
28 Correct 1271 ms 27256 KB Output is correct
29 Correct 2802 ms 27768 KB Output is correct
30 Correct 1646 ms 24412 KB Output is correct
31 Correct 1599 ms 23156 KB Output is correct
32 Correct 239 ms 16120 KB Output is correct
33 Correct 1271 ms 27256 KB Output is correct
34 Correct 2784 ms 27644 KB Output is correct
35 Correct 1779 ms 24184 KB Output is correct
36 Correct 1644 ms 23160 KB Output is correct
37 Correct 1125 ms 28664 KB Output is correct
38 Correct 2377 ms 41720 KB Output is correct