## Submission #347992

# Submission time Handle Problem Language Result Execution time Memory
347992 2021-01-14T02:40:22 Z amunduzbaev Tropical Garden (IOI11_garden) C++14
49 / 100
71 ms 46052 KB
```/** made by amunduzbaev **/

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Pi acos(-1);
#define mod 1e9+7
#define inf 1e18

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}

const int NN = 3e5+5;

vii edges[NN];
vii gg[NN];
int bup[NN];
ll cnt;
stack<int> ss;
vii cyc[NN];
int goal, oncyc[NN], last, used[NN], len[NN], in[NN];

void dfs(int u){
//cout<<u<<" ";
if(used[u] && in[u]){
oncyc[u] = ++last;
cyc[last].pb(u);
while(!ss.empty() && ss.top() != u){
oncyc[ss.top()] = last;
cyc[last].pb(ss.top());
ss.pop();
}
len[last] = sz(cyc[last]);
return;
}
if(used[u]) return;

used[u] = 1;
ss.push(u);
in[u] = 1;
dfs(bup[u]);
in[u] = 0;
if(!ss.empty()) ss.pop();
}

int tin[NN], tout[NN], tim;
int rr[NN], dd[NN], ddr[NN];

void treepr(int u, int root){
//cout<<u<<" ";
rr[u] = root;
tin[u] = ++tim;
for(auto x:edges[u]){
if(oncyc[x]) continue;
//cout<<x<<" ";
ddr[x] = ddr[u]+1;
treepr(x, root);
}
//cout<<"no\n";
tout[u] = ++tim;
}

bool check(int u, int k, int goal){
//cout<<u<<" "<<goal<<" "<<k<<"\n";
if(oncyc[u] && oncyc[goal] && oncyc[u] == oncyc[goal]){
k %= len[oncyc[u]];
return (dd[u] == k);
}

if(oncyc[u]) return 0;

if(oncyc[goal]){
k -= ddr[u];
u = rr[u];
if(k < 0) return 0;
if(oncyc[u] != oncyc[goal]) return 0;
k %= len[oncyc[u]];
return (dd[u] == k);
}

if(tin[goal] < tin[u] && tout[goal] > tout[u])
return (ddr[u] - ddr[goal] == k);

return 0;
}

void count_routes(int n, int m, int p, int R[][2], int q, int kk[]){
for(int i=0; i<m; i++){
int a = R[i][0], b = R[i][1];
if(sz(gg[a]) < 2) gg[a].pb(b);
if(sz(gg[b]) < 2) gg[b].pb(a);
}

memset(rr, -1, sizeof rr);
memset(bup, -1, sizeof bup);

for(int i=0;i<n;i++){
for(int j=0;j<sz(gg[i]);j++){
int to = gg[i][j];
if(gg[to][0] == i && sz(gg[to]) > 1){
bup[i + j * n] = to+n;
edges[to+n].pb(i + j*n);
}else{
bup[i + j * n] = to;
edges[to].pb(i + j*n);
}
}
}
goal = p;

for(int i=0;i<2*n;i++){
if(used[i]) continue;
while(!ss.empty()) ss.pop();
dfs(i);
}

for(int i=1;i<=last;i++){
for(auto x:cyc[i]) treepr(x, x); //cout<<"\n"; }
}

if(oncyc[p]){
//memset(used, 0, sizeof used);
int cur = p, dis = 0;
while(cur != p || dis == 0){
dd[cur] = dis++;
for(auto x:edges[cur]){
if(oncyc[x] != oncyc[cur]) continue;
cur = x;
break;
}
}
}

if(oncyc[p+n]){
//memset(used, 0 ,sizeof used);
int cur = p+n, dis = 0;
while(cur != p+n || dis == 0){
//cout<<cur<<" ";
dd[cur] = dis++;
for(auto x:edges[cur]){
if(oncyc[x] != oncyc[cur]) continue;
cur = x;
break;
}
}  // cout<<"\n";
}

for(int i=0;i<q;i++){
int cnt = 0;
for(int j=0;j<n;j++){
cnt += ( check(j, kk[i], p) | check(j, kk[i], p+n) );
//if(cnt) cout<<j<<"\n";
}
}
}

/*

6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2

5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
1 2

*/
```

#### Subtask #1 49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 16 ms 24044 KB Output is correct
3 Correct 16 ms 24044 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 16 ms 24172 KB Output is correct
7 Correct 15 ms 23916 KB Output is correct
8 Correct 20 ms 24044 KB Output is correct
9 Correct 18 ms 24044 KB Output is correct

#### Subtask #2 0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 16 ms 24044 KB Output is correct
3 Correct 16 ms 24044 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 16 ms 24172 KB Output is correct
7 Correct 15 ms 23916 KB Output is correct
8 Correct 20 ms 24044 KB Output is correct
9 Correct 18 ms 24044 KB Output is correct
10 Correct 15 ms 23916 KB Output is correct
11 Correct 28 ms 26988 KB Output is correct
12 Correct 48 ms 28672 KB Output is correct
13 Incorrect 71 ms 46052 KB Output isn't correct
14 Halted 0 ms 0 KB -

#### Subtask #3 0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 16 ms 24044 KB Output is correct
3 Correct 16 ms 24044 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 16 ms 24172 KB Output is correct
7 Correct 15 ms 23916 KB Output is correct
8 Correct 20 ms 24044 KB Output is correct
9 Correct 18 ms 24044 KB Output is correct
10 Correct 15 ms 23916 KB Output is correct
11 Correct 28 ms 26988 KB Output is correct
12 Correct 48 ms 28672 KB Output is correct
13 Incorrect 71 ms 46052 KB Output isn't correct
14 Halted 0 ms 0 KB -