#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
reverse the order of queries, deal with addition of edges instead of removal of edges
what we have is a functional graph
when we root a cc of the graph at a cycle, we have a directed tree going into the cycle
do the same for all ccs
we have multiple forests, with root node = the cycle
for the ease of implementation, assume the tree is rooted away from the cycle (direction of edges are reversed)
for (u,v) to be connected in the directed graph, they also have to be connected in the undirected graph
use a dsu to maintain the ccs
if (u,v) dont belong to the same cc in the dsu, then there is no path
assume there is a path between (u,v)
from a given edge u, we can only go to its ancestor in the tree
if v does not belong to a cycle (i.e is not a root node), then just check if v is an ances of u (using in and out times)
if yes, then ans = depth[u]-depth[v]
what if v belongs to a cycle?
by going up from u, we should be able to reach the same cycle as v (ans = -1 otherwise)
find the first node that we would reach on the cycle
for each cycle, maintain a fenwick, where fenw[i] = 1 if the outgoing edge of the ith node in the cycle is activated
checking if there is a directed path from u --> v is now possible (with some casework)
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
template<typename T>
struct fenwick {
int siz;
vector<T> tree;
fenwick() {
}
fenwick(int n) {
siz = n;
tree = vector<T>(n + 1);
}
int lsb(int x) {
return x & -x;
}
void build(vector<T> &a, int n) {
for (int i = 1; i <= n; ++i) {
int par = i + lsb(i);
tree[i] += a[i];
if (par <= siz) {
tree[par] += tree[i];
}
}
}
void pupd(int i, T v) {
while (i <= siz) {
tree[i] += v;
i += lsb(i);
}
}
T sum(int i) {
T res = 0;
while (i) {
res += tree[i];
i -= lsb(i);
}
return res;
}
T query(int l, int r) {
if (l > r) return 0;
T res = sum(r) - sum(l - 1);
return res;
}
};
struct DSU {
vector<int> par, rankk, siz;
DSU() {
}
DSU(int n) {
init(n);
}
void init(int n) {
par = vector<int>(n + 1);
rankk = vector<int>(n + 1);
siz = vector<int>(n + 1);
rep(i, n + 1) create(i);
}
void create(int u) {
par[u] = u;
rankk[u] = 0;
siz[u] = 1;
}
int find(int u) {
if (u == par[u]) return u;
else return par[u] = find(par[u]);
}
bool same(int u, int v) {
return find(u) == find(v);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (rankk[u] == rankk[v]) rankk[u]++;
if (rankk[u] < rankk[v]) swap(u, v);
par[v] = u;
siz[u] += siz[v];
}
};
vector<ll> adj[N];
vector<bool> vis(N);
vector<ll> tin(N), tout(N);
vector<ll> depth(N);
vector<ll> root(N);
ll timer = 1;
void dfs1(ll u, ll r){
vis[u] = 1;
tin[u] = timer++;
root[u] = r;
trav(v,adj[u]){
if(vis[v]) conts;
depth[v] = depth[u]+1;
dfs1(v,r);
}
tout[u] = timer-1;
}
void solve(int test_case)
{
ll n; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
rep1(i,n){
if(!a[i]){
a[i] = i;
}
}
queue<ll> q;
vector<bool> bad(n+5);
vector<ll> indeg(n+5);
rep1(i,n){
adj[a[i]].pb(i);
indeg[a[i]]++;
}
rep1(i,n){
if(indeg[i] == 0){
q.push(i);
}
}
while(!q.empty()){
ll u = q.front();
q.pop();
bad[u] = 1;
indeg[a[u]]--;
if(indeg[a[u]] == 0){
q.push(a[u]);
}
}
vector<ll> cyc_id(n+5), cyc_pos(n+5), cyc_siz(n+5);
ll ptr = 0;
rep1(i,n){
if(bad[i] or vis[i]) conts;
ll j = i;
vector<ll> roots;
ptr++;
ll curr_pos = 1;
while(!vis[j]){
vis[j] = 1;
roots.pb(j);
cyc_id[j] = ptr;
cyc_pos[j] = curr_pos++;
j = a[j];
}
cyc_siz[ptr] = sz(roots);
trav(r,roots){
dfs1(r,r);
}
}
fenwick<ll> fenw[ptr+5];
rep1(i,ptr){
fenw[i] = fenwick<ll>(cyc_siz[i]);
}
ll m; cin >> m;
vector<array<ll,3>> queries(m+5);
vector<bool> rem(n+5);
rep1(i,m){
ll t; cin >> t;
if(t == 1){
ll u; cin >> u;
queries[i] = {t,u,-1};
rem[u] = 1;
}
else{
ll u,v; cin >> u >> v;
queries[i] = {t,u,v};
}
}
DSU dsu(n+5);
auto activate = [&](ll u){
dsu.merge(u,a[u]);
if(!bad[u]){
ll id = cyc_id[u];
ll pos = cyc_pos[u];
fenw[id].pupd(pos,1);
}
};
rep1(i,n){
if(!rem[i]){
activate(i);
}
}
vector<ll> ans(m+5);
rev(i,m,1){
auto [t,u,v] = queries[i];
if(t == 1){
activate(u);
}
else{
if(!dsu.same(u,v)){
ans[i] = -1;
conts;
}
if(bad[v]){
if(!(tin[v] <= tin[u] and tout[v] >= tout[u])){
ans[i] = -1;
conts;
}
ans[i] = depth[u]-depth[v];
conts;
}
ll rootu = root[u];
if(cyc_id[rootu] != cyc_id[v]){
ans[i] = -1;
conts;
}
ans[i] = depth[u];
ll id = cyc_id[rootu];
ll l = cyc_pos[rootu], r = cyc_pos[v];
if(l <= r){
if(fenw[id].query(l,r-1) == r-l){
ans[i] += r-l;
}
else{
ans[i] = -1;
}
}
else{
ll siz = cyc_siz[id];
ll sum = fenw[id].query(l,siz)+fenw[id].query(1,r-1);
ll len = siz-l+r;
if(sum == len){
ans[i] += len;
}
else{
ans[i] = -1;
}
}
}
}
rep1(i,m){
if(queries[i][0] == 2){
cout << ans[i] << endl;
}
}
}
int main()
{
fastio;
int t = 1;
// cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
5980 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5980 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5980 KB |
Output is correct |
| 4 |
Correct |
5 ms |
6236 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5980 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6780 KB |
Output is correct |
| 7 |
Correct |
7 ms |
6744 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6744 KB |
Output is correct |
| 9 |
Correct |
7 ms |
6748 KB |
Output is correct |
| 10 |
Correct |
8 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
45 ms |
18364 KB |
Output is correct |
| 12 |
Correct |
51 ms |
15080 KB |
Output is correct |
| 13 |
Correct |
47 ms |
17040 KB |
Output is correct |
| 14 |
Correct |
36 ms |
14376 KB |
Output is correct |
| 15 |
Correct |
40 ms |
15304 KB |
Output is correct |
| 16 |
Correct |
43 ms |
15196 KB |
Output is correct |
| 17 |
Correct |
47 ms |
19264 KB |
Output is correct |
| 18 |
Correct |
51 ms |
19268 KB |
Output is correct |
| 19 |
Correct |
51 ms |
19176 KB |
Output is correct |
| 20 |
Correct |
46 ms |
18552 KB |
Output is correct |
