| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 84464 | 2018-11-15T09:15:50 Z | ekrem | 특수한 그래프 (IZhO13_specialg) | C++ | 24 ms | 24568 KB |
//Boyle sorunun amk
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;
typedef long long ll;
ll n, q, m, cem, a[N], b[N], c[N], git[25][N], t[N], ag[N];
ll x[N], yer[N], u[N], der[N], amk[N], ata[N], fen[N];
vector < ll > g[N], ans;
ll atabul(ll x){
if(ata[x] != x)
ata[x] = atabul(ata[x]);
return ata[x];}
void up(ll x, ll y){
for(; x <= m; x += x&-x)
fen[x] += y;}
ll qu(ll x){
if(x == 0)
return 0;
ll top = 0;
for(; x > 0; x -= x&-x)
top += fen[x];
return top;}
void hazirla();
void dfs(ll node){
u[node] = 1;
if(u[git[0][node]]){
cem = node;
return;
}
dfs(git[0][node]);}
void dfs2(ll node, ll dr, ll at){
ag[node] = at;
der[node] = dr;
for(ll i = 0; i < g[node].size(); i++)
dfs2(g[node][i], dr + 1, at);}
ll lca(ll x, ll y){
ll ans = 0;
for(ll i = 21; i >= 0; i--){
// cout << x << " " << y << endl;
if(der[y] <= der[git[i][x]] and (1<<i) <= der[x]){
ans += 1<<i;
x = git[i][x];
}
}
if(x == y)
return ans;
return -1;}
ll yolver(ll x, ll y){
ll i = yer[x];
ll j = yer[y];
if(i <= j){
ll ara = qu(j - 1) - qu(i - 1);
if(ara)
return -1;
return j - i;
}
ll ara = qu(m) - qu(i - 1) + qu(j - 1);
if(ara)
return -1;
return m - i + j;}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%lld",&n);
for(ll i = 1; i <= n; i++){
scanf("%lld",&git[0][i]);
amk[i] = git[0][i];
}
hazirla();
for(ll i = 1; i <= n; i++){
if(yer[i])
continue;
g[git[0][i]].pb(i);
}
for(ll i = 1; i <= m; i++)
dfs2(x[i], 0, x[i]);
scanf("%lld",&q);
for(ll i = 1; i <= q; i++){
scanf("%lld %lld",c + i, a + i);
if(c[i] == 2)
scanf("%lld", b + i);
else{
if(yer[a[i]] == 0)
amk[a[i]] = 0;
else
up(yer[a[i]], 1);
c[i] = git[0][i];
}
}
for(ll i = 1; i <= n; i++)
if(amk[i]){
ll xx = atabul(i);
ll yy = atabul(amk[i]);
if(xx != yy)
ata[xx] = yy;
}
// for(ll i = 1; i <= n; i++)cout << ag[i] << " ";cout << endl;
for(ll i = q; i >= 1; i--){
if(c[i] == 2){
ll xx = atabul(a[i]);
ll yy = atabul(b[i]);
if(xx != yy){
ans.pb(-1);
continue;
}
// cout << a[i] << " " << b[i] << "AMKXX" << endl;
ll l;;
if(ag[b[i]] != ag[a[i]])
l = ag[a[i]];
else
l = b[i];
ll yol = lca(a[i], l);
// cout << a[i] << " " << l << " e yol = " << yol << endl;
if(yol == -1){
ans.pb(-1);
continue;
}
if(l != b[i]){
ll orz = yolver(l, b[i]);
// cout << l << " " << b[i] << " = " << orz << endl;
if(orz == -1)
ans.pb(-1);
else
ans.pb(yol + orz);
} else
ans.pb(yol);
}
else{
if(yer[a[i]] == 0){
ll xx = atabul(a[i]);
ll yy = atabul(git[0][a[i]]);
// cout << "YOl eklendi " << a[i] << " -> "<<git[0][a[i]] << endl;
if(xx != yy)
ata[xx] = yy;
}
else{
// cout << yer[a[i]] << " bir eksiltildi" << endl;
up(yer[a[i]], -1);
}
}
}
reverse(ans.begin(), ans.end());
for(ll i = 0; i < ans.size(); i++)
printf("%lld\n", ans[i]);
return 0;
}
void hazirla(){
for(ll i = 1; i <= 21; i++)
for(ll j = 1; j <= n; j++)
git[i][j] = git[i - 1][git[i - 1][j]];
dfs(1);
ll node = cem;
while(1){
x[++m] = node;
yer[node] = m;
node = git[0][node];
if(node == cem)
break;
}
for(ll i = 1; i <= n; i++)
ata[i] = i;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 24 ms | 24568 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |