oj.uz

Submission #347994

# Submission time Handle Problem Language Result Execution time Memory
347994 2021-01-14T02:45:16 Z amunduzbaev Tropical Garden (IOI11_garden) C++14
49 / 100
 74 ms 50020 KB 
/** made by amunduzbaev **/

#include "garden.h"
#include "gardenlib.h"
//#include "grader.cpp"
#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 = 5e5+5;
 
vii edges[NN];
vii gg[NN];
int bup[NN];
ll cnt;
stack<int> ss;
vii cyc;
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.pb(u);
		while(!ss.empty() && ss.top() != u){
			oncyc[ss.top()] = last;
			cyc.pb(ss.top());
			ss.pop();
		}
		len[last] = sz(cyc);
		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();
		cyc.clear();
		dfs(i);
		for(auto x:cyc) treepr(x, x); 
	}
	
	if(oncyc[p]){
		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]){
		int cur = p+n, dis = 0;
		while(cur != p+n || dis == 0){
			dd[cur] = dis++;
			for(auto x:edges[cur]){
				if(oncyc[x] != oncyc[cur]) continue;
				cur = x;
				break;
			}
		}
	}
	
	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) );
		
		answer(cnt);
	}
}

/*

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 18 ms 28140 KB Output is correct
2 Correct 18 ms 28012 KB Output is correct
3 Correct 18 ms 28012 KB Output is correct
4 Correct 17 ms 27884 KB Output is correct
5 Correct 17 ms 27756 KB Output is correct
6 Correct 18 ms 28012 KB Output is correct
7 Correct 18 ms 27756 KB Output is correct
8 Correct 21 ms 27884 KB Output is correct
9 Correct 20 ms 28012 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28140 KB Output is correct
2 Correct 18 ms 28012 KB Output is correct
3 Correct 18 ms 28012 KB Output is correct
4 Correct 17 ms 27884 KB Output is correct
5 Correct 17 ms 27756 KB Output is correct
6 Correct 18 ms 28012 KB Output is correct
7 Correct 18 ms 27756 KB Output is correct
8 Correct 21 ms 27884 KB Output is correct
9 Correct 20 ms 28012 KB Output is correct
10 Correct 17 ms 27756 KB Output is correct
11 Correct 30 ms 30828 KB Output is correct
12 Correct 51 ms 32512 KB Output is correct
13 Incorrect 74 ms 50020 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28140 KB Output is correct
2 Correct 18 ms 28012 KB Output is correct
3 Correct 18 ms 28012 KB Output is correct
4 Correct 17 ms 27884 KB Output is correct
5 Correct 17 ms 27756 KB Output is correct
6 Correct 18 ms 28012 KB Output is correct
7 Correct 18 ms 27756 KB Output is correct
8 Correct 21 ms 27884 KB Output is correct
9 Correct 20 ms 28012 KB Output is correct
10 Correct 17 ms 27756 KB Output is correct
11 Correct 30 ms 30828 KB Output is correct
12 Correct 51 ms 32512 KB Output is correct
13 Incorrect 74 ms 50020 KB Output isn't correct
14 Halted 0 ms 0 KB -