oj.uz

Submission #339418

# Submission time Handle Problem Language Result Execution time Memory
339418 2020-12-25T07:55:59 Z tengiz05 Special graph (IZhO13_specialg) C++17
0 / 100
 1000 ms 5992 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool ckmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool ckmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 1e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k;
int nex[N];
int ans[N];
bool black[N];
int dist;
int looking_for;
bool found;
vector<bool> used;
void dfs(int u, int d=0){
	if(u == looking_for){
		dist = d;
		found = true;
		return;
	}
	used[u] = true;
	if(!used[nex[u]])dfs(nex[u],d+1);
}
void solve(int test_case){
	int i, j, numq;
	cin >> n;
	for(i=1;i<=n;i++){
		cin >> nex[i];
	}
	vector<tuple<int,int,int>> Q;
	cin >> numq;
	for(i=0;i<numq;i++){
		int typ;
		cin >> typ;
		if(typ == 1){
			int t;
			cin >> t;
			Q.pb(make_tuple(typ,t,0));
			black[t] = true;
		}else {
			int l, r;
			cin >> l >> r;
			Q.pb(make_tuple(typ,l,r));
		}
	}
//	reverse(all(Q));
	for(i=0;i<numq;i++){
		found = false;
		auto [typ, l, r] = Q[i];
		if(typ == 2){
			used.assign(n+1, 0);
			looking_for = r;
			dfs(l);
			if(found)ans[i] = dist;
			else ans[i] = -1;
		}else {
			nex[l] = 0;
		}
	}
	for(i=0;i<numq;i++){
		if(get<0>(Q[i]) == 2)cout << ans[i] << '\n';
	}
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

specialg.cpp: In function 'void solve(long long int)':
specialg.cpp:34:9: warning: unused variable 'j' [-Wunused-variable]
   34 |  int i, j, numq;
      |         ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 4 ms 940 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 23 ms 1512 KB Output is correct
7 Correct 24 ms 1512 KB Output is correct
8 Correct 26 ms 1512 KB Output is correct
9 Correct 22 ms 1512 KB Output is correct
10 Correct 27 ms 1512 KB Output is correct
11 Execution timed out 1099 ms 5992 KB Time limit exceeded
12 Halted 0 ms 0 KB -