oj.uz

Submission #225604

# Submission time Handle Problem Language Result Execution time Memory
225604 2020-04-20T23:12:14 Z AmineWeslati Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 4864 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

//#include <cassert>
// #include "grader.h"

using namespace std;

typedef string str;
typedef long long ll;
//#define int ll
typedef double db;
typedef long double ld;

typedef pair<int,int> pi;
#define mp make_pair
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;

#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int MXN=150000+1;

//int N, M, P, R[MXN][2], Q, G[2001];

int ans;
int V,E,D;
vpi g[MXN];
int num;
vi p;

void dfs(int u, int c){
   if(c==num && u==D){ans++; return;}
   if(c==num) return;
   int mx=0,v=-1;
   for (auto x: g[u]){
      if(g[u].size()==1){ v=x.fi; break;}
      if(x.se>mx && p[u]!=x.fi){mx=x.se; v=x.fi;}
   }
   p[v]=u;
   dfs(v,c+1);
   return;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
   V=N; E=M; D=P;
   int w=E;
   for (int i=0; i<E; i++){
      int a=R[i][0],b=R[i][1];
      g[a].pb({b,w});
      g[b].pb({a,w});
      w--;
   }
   for (int q=0; q<Q; q++){
      ans=0; num=G[q];
      for (int i=0; i<V; i++){p.assign(V,-1); dfs(i,0);}
      answer(ans);
   }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3840 KB Output is correct
2 Correct 8 ms 3968 KB Output is correct
3 Correct 8 ms 3968 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 6 ms 3840 KB Output is correct
6 Correct 9 ms 3968 KB Output is correct
7 Correct 7 ms 3968 KB Output is correct
8 Correct 8 ms 3840 KB Output is correct
9 Correct 12 ms 4096 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3840 KB Output is correct
2 Correct 8 ms 3968 KB Output is correct
3 Correct 8 ms 3968 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 6 ms 3840 KB Output is correct
6 Correct 9 ms 3968 KB Output is correct
7 Correct 7 ms 3968 KB Output is correct
8 Correct 8 ms 3840 KB Output is correct
9 Correct 12 ms 4096 KB Output is correct
10 Correct 15 ms 3968 KB Output is correct
11 Execution timed out 5061 ms 4864 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3840 KB Output is correct
2 Correct 8 ms 3968 KB Output is correct
3 Correct 8 ms 3968 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 6 ms 3840 KB Output is correct
6 Correct 9 ms 3968 KB Output is correct
7 Correct 7 ms 3968 KB Output is correct
8 Correct 8 ms 3840 KB Output is correct
9 Correct 12 ms 4096 KB Output is correct
10 Correct 15 ms 3968 KB Output is correct
11 Execution timed out 5061 ms 4864 KB Time limit exceeded
12 Halted 0 ms 0 KB -