oj.uz

Submission #1104594

# Submission time Handle Problem Language Result Execution time Memory
1104594 2024-10-24T06:07:02 Z kungarooo Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 27804 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#define B 150000
using namespace std;
vector<int> v(2*B);
vector<vector<int>> adj(B),T(B*2);
vector<bool> vis(2*B);
int sz=0;
int* G;
bool findcyclic(int x,int st){
  if(vis[x]&&x==st)return 1;
  else if(vis[x])return 0;
  vis[x]=1;
  sz++;
  bool ret=findcyclic(v[x],st);
  vis[x]=0;
  return ret;
}
int bfs(int x,int ii,int sz){
  queue<pair<int,int>> q;
  vector<bool> vv(B*2);
  q.push({x,0});
  int ans=0;
  while(!q.empty()){
    int node=q.front().first,we=q.front().second;
    q.pop();
    if(we>G[ii]||vv[node])continue;
    vv[node]=1;
    if(sz==0){
      if(we==G[ii]&&node<B)ans++;
    }else{
      if(0==(G[ii]-we)%sz&&node<B)ans++;
    }
    for(auto i:T[node]){
      if(!vv[i]&&we<G[ii])q.push({i,we+1});
    }
  }
  return ans;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
  ::G=G;
  for(int i=0;i<M;i++){
    adj[R[i][0]].push_back(R[i][1]);
    adj[R[i][1]].push_back(R[i][0]);
  }
  for(int i=0;i<N;i++){
    if(i==adj[adj[i][0]][0])v[i]=adj[i][0]+B;
    else v[i]=adj[i][0];
    if(adj[i].size()>=2){
      if(adj[adj[i][1]][0]==i)v[B+i]=adj[i][1]+B;
      else v[B+i]=adj[i][1];
    }
    else v[B+i]=v[i];
  }
  int sz1=0,sz2=0;
  if(findcyclic(P,P)){
    sz1=sz;
  }
  sz=0;
  if(findcyclic(P+B,P+B)){
    sz2=sz;
  }
  sz=0;
  for(int i=0;i<N;i++){
    T[v[i]].push_back(i);
    T[v[i+B]].push_back(i+B);
  }
  for(int i=0;i<Q;i++)answer(bfs(P,i,sz1)+bfs(P+B,i,sz2));
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12112 KB Output is correct
2 Correct 5 ms 12368 KB Output is correct
3 Correct 4 ms 12308 KB Output is correct
4 Correct 5 ms 12112 KB Output is correct
5 Correct 5 ms 12112 KB Output is correct
6 Correct 5 ms 12368 KB Output is correct
7 Correct 5 ms 12112 KB Output is correct
8 Correct 5 ms 12112 KB Output is correct
9 Correct 6 ms 12368 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12112 KB Output is correct
2 Correct 5 ms 12368 KB Output is correct
3 Correct 4 ms 12308 KB Output is correct
4 Correct 5 ms 12112 KB Output is correct
5 Correct 5 ms 12112 KB Output is correct
6 Correct 5 ms 12368 KB Output is correct
7 Correct 5 ms 12112 KB Output is correct
8 Correct 5 ms 12112 KB Output is correct
9 Correct 6 ms 12368 KB Output is correct
10 Correct 5 ms 12112 KB Output is correct
11 Correct 13 ms 15952 KB Output is correct
12 Correct 21 ms 17044 KB Output is correct
13 Correct 42 ms 27708 KB Output is correct
14 Correct 59 ms 23376 KB Output is correct
15 Correct 71 ms 23520 KB Output is correct
16 Correct 49 ms 20820 KB Output is correct
17 Correct 57 ms 20040 KB Output is correct
18 Correct 22 ms 16976 KB Output is correct
19 Correct 55 ms 23304 KB Output is correct
20 Correct 65 ms 23664 KB Output is correct
21 Correct 49 ms 20808 KB Output is correct
22 Correct 47 ms 20040 KB Output is correct
23 Correct 63 ms 24136 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12112 KB Output is correct
2 Correct 5 ms 12368 KB Output is correct
3 Correct 4 ms 12308 KB Output is correct
4 Correct 5 ms 12112 KB Output is correct
5 Correct 5 ms 12112 KB Output is correct
6 Correct 5 ms 12368 KB Output is correct
7 Correct 5 ms 12112 KB Output is correct
8 Correct 5 ms 12112 KB Output is correct
9 Correct 6 ms 12368 KB Output is correct
10 Correct 5 ms 12112 KB Output is correct
11 Correct 13 ms 15952 KB Output is correct
12 Correct 21 ms 17044 KB Output is correct
13 Correct 42 ms 27708 KB Output is correct
14 Correct 59 ms 23376 KB Output is correct
15 Correct 71 ms 23520 KB Output is correct
16 Correct 49 ms 20820 KB Output is correct
17 Correct 57 ms 20040 KB Output is correct
18 Correct 22 ms 16976 KB Output is correct
19 Correct 55 ms 23304 KB Output is correct
20 Correct 65 ms 23664 KB Output is correct
21 Correct 49 ms 20808 KB Output is correct
22 Correct 47 ms 20040 KB Output is correct
23 Correct 63 ms 24136 KB Output is correct
24 Correct 8 ms 12112 KB Output is correct
25 Correct 124 ms 16008 KB Output is correct
26 Correct 70 ms 17116 KB Output is correct
27 Execution timed out 5057 ms 27804 KB Time limit exceeded
28 Halted 0 ms 0 KB -