oj.uz

답안 #347992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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 "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 = 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";
		}
		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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -