oj.uz

Submission #1104596

# Submission time Handle Problem Language Result Execution time Memory
1104596 2024-10-24T06:09:59 Z kungarooo Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 39500 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#define B 300000
using namespace std;
vector<int> v(2*B);
vector<vector<int>> adj(B),T(B*2);
vector<bool> vis(2*B);
int sz=0;
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>ii||vv[node])continue;
    vv[node]=1;
    if(sz==0){
      if(we==ii&&node<B)ans++;
    }else{
      if(0==(ii-we)%sz&&node<B)ans++;
    }
    for(auto i:T[node]){
      if(!vv[i])q.push({i,we+1});
    }
  }
  return ans;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int 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,G[i],sz1)+bfs(P+B,G[i],sz2));
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24144 KB Output is correct
2 Correct 7 ms 24344 KB Output is correct
3 Correct 6 ms 24144 KB Output is correct
4 Correct 6 ms 23888 KB Output is correct
5 Correct 6 ms 23888 KB Output is correct
6 Correct 7 ms 24144 KB Output is correct
7 Correct 6 ms 23888 KB Output is correct
8 Correct 6 ms 24144 KB Output is correct
9 Correct 7 ms 24144 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24144 KB Output is correct
2 Correct 7 ms 24344 KB Output is correct
3 Correct 6 ms 24144 KB Output is correct
4 Correct 6 ms 23888 KB Output is correct
5 Correct 6 ms 23888 KB Output is correct
6 Correct 7 ms 24144 KB Output is correct
7 Correct 6 ms 23888 KB Output is correct
8 Correct 6 ms 24144 KB Output is correct
9 Correct 7 ms 24144 KB Output is correct
10 Correct 6 ms 23888 KB Output is correct
11 Correct 13 ms 27984 KB Output is correct
12 Correct 22 ms 28752 KB Output is correct
13 Correct 48 ms 39500 KB Output is correct
14 Correct 66 ms 35164 KB Output is correct
15 Correct 76 ms 35400 KB Output is correct
16 Correct 57 ms 32860 KB Output is correct
17 Correct 55 ms 32072 KB Output is correct
18 Correct 24 ms 28776 KB Output is correct
19 Correct 70 ms 35144 KB Output is correct
20 Correct 72 ms 35396 KB Output is correct
21 Correct 59 ms 32584 KB Output is correct
22 Correct 58 ms 31860 KB Output is correct
23 Correct 70 ms 35912 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24144 KB Output is correct
2 Correct 7 ms 24344 KB Output is correct
3 Correct 6 ms 24144 KB Output is correct
4 Correct 6 ms 23888 KB Output is correct
5 Correct 6 ms 23888 KB Output is correct
6 Correct 7 ms 24144 KB Output is correct
7 Correct 6 ms 23888 KB Output is correct
8 Correct 6 ms 24144 KB Output is correct
9 Correct 7 ms 24144 KB Output is correct
10 Correct 6 ms 23888 KB Output is correct
11 Correct 13 ms 27984 KB Output is correct
12 Correct 22 ms 28752 KB Output is correct
13 Correct 48 ms 39500 KB Output is correct
14 Correct 66 ms 35164 KB Output is correct
15 Correct 76 ms 35400 KB Output is correct
16 Correct 57 ms 32860 KB Output is correct
17 Correct 55 ms 32072 KB Output is correct
18 Correct 24 ms 28776 KB Output is correct
19 Correct 70 ms 35144 KB Output is correct
20 Correct 72 ms 35396 KB Output is correct
21 Correct 59 ms 32584 KB Output is correct
22 Correct 58 ms 31860 KB Output is correct
23 Correct 70 ms 35912 KB Output is correct
24 Correct 12 ms 24056 KB Output is correct
25 Correct 123 ms 27984 KB Output is correct
26 Correct 79 ms 26956 KB Output is correct
27 Execution timed out 5064 ms 38092 KB Time limit exceeded
28 Halted 0 ms 0 KB -