Weekly Training Farm 22 is over. Congratulations to the winners :↵
↵
1. [user:W4yneb0t,2017-01-20] (perfect score in < 1 hour!)↵
↵
2. [user:aaaaajack,2017-01-20] (perfect score)↵
↵
3. [user:eddy1021,2017-01-20]↵
↵
Here is the editorial :↵
↵
### Problem A ↵
↵
This problem can be solved by greedy. We list down the positive integers one by one. We keep a pointer that initially points to the first letter of $s$. Whenever the pointed character in the string $s$ matches the corresponding digit of the integer, we move the pointer one step to the right and continue. Repeat this process until the pointer reaches the end. ↵
↵
However, we still need to know whether the answer can be large. The key is to note that the answer will never exceed $10^{6}$, because after writing down $10$ consecutive numbers, at least one of them has last digit equals to the current digit, so the pointer will move to the right at least once when we write down $10$ consecutive numbers. Thus, in the worse case, we'll only list down the numbers from $1$ to $10^{6}$, which is definitely fast enough.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
vector<pair<char,int> > vec;↵
const int N = 100000;↵
↵
void gen()↵
{↵
for(int i = 1; i <= N*10; i++)↵
{↵
int x=i;↵
string r;↵
while(x)↵
{↵
r+=char('0'+x%10);↵
x/=10;↵
}↵
for(int j = int(r.size())-1;j>=0;j--)↵
{↵
vec.pb(mp(r[j],i));↵
} ↵
}↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
gen();↵
string s; cin>>s;↵
int ptr=0; int p2 = 0;↵
while(p2<s.length()&&ptr<vec.size())↵
{↵
if(s[p2]==vec[ptr].fi) ↵
{↵
p2++;↵
ptr++;↵
continue;↵
}↵
ptr++;↵
}↵
ptr--; //remember this↵
cout<<vec[ptr].se;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
### Problem B↵
↵
This problem can be solved using dynamic programming. Firstly, observe that if we already determine which set of problems to solve, then it's best to solve the problem in increasing order of time needed to solve in order to minimize the time penalty. Thus, we can first sort the problems in increasing order of time needed, breaking ties arbitarily.↵
↵
Let $dp[i][j]$ denote the maximum number of problems solved and minimum time penalty acquired when doing so by using exactly $j$ minutes and only solving problems among the first $i$ ones. $dp[0][0] = (0, 0)$ (the first integer denotes the number of problems solved and the second integer denotes the time penalty in order to do so). The transitions can be handled easily by simply considering whether to solve the $i$-th problem or not. The time complexity of this solution is $O(nT)$ ($T$ is the duration of the contest)↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
const int N = 100011;↵
const int T = 301;↵
ii dp[N][T];↵
ii a[N];↵
↵
ii maxi(ii a, ii b)↵
{↵
if(a.fi!=b.fi)↵
{↵
if(a.fi>b.fi) return a;↵
else return b;↵
}↵
else↵
{↵
if(a.se<b.se) return a;↵
else return b;↵
}↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
int n; cin>>n;↵
int t = 300;↵
for(int i = 1; i <= n; i++)↵
{↵
cin>>a[i].fi>>a[i].se;↵
}↵
sort(a+1,a+n+1);↵
for(int i = 0; i <= n; i++)↵
{↵
for(int j = 0; j <= t; j++)↵
{↵
dp[i][j]=mp(-1,-1);↵
}↵
}↵
dp[0][0] = mp(0,0);↵
ii maxans = mp(0,0);↵
for(int i = 1; i <= n; i++)↵
{↵
for(int j = 0; j <= 300; j++)↵
{↵
dp[i][j] = dp[i-1][j];↵
if(j-a[i].fi>=0&&dp[i-1][j-a[i].fi].fi!=-1)↵
{↵
dp[i][j] = maxi(dp[i][j], mp(dp[i-1][j-a[i].fi].fi+1, dp[i-1][j-a[i].fi].se+j+20LL*a[i].se));↵
}↵
if(i==n) maxans = maxi(maxans, dp[i][j]);↵
}↵
}↵
cout<<maxans.fi<<' '<<maxans.se<<'\n';↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### Problem C↵
↵
This is an ad hoc problem. Firstly, we can use two moves to determine what the value of the first bit is. (simply flipping it twice will tell you its value. Now, if the bit is $1$, you don't need to flip it anymore. If it's $0$, you'll need to flip it. In any case, we'll flip the second bit as well. (if the first bit needs to be flipped, we'll flip $[1, 2]$ and flip $[2, 2]$ otherwise) After flipping the second bit, we can determine whether it's a $1$ or $0$ by calculating from the total number of $1$s of the string before the flip and after the flip. We can repeat this for every $2$ consecutive bits until we arrive at the last two bits. At this point, we know what the second last bit is, and we also know the total number of $1$ bits. So, we can easily deduce the value of the last bit from the information as well. Now, we just need to perform one last flip to make the last $2$ bits become $1$. The total number of moves made is $n + 1$.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
int flip(int l, int r)↵
{↵
cout<<l<<' '<<r<<'\n';↵
fflush(stdout);↵
int cnt; ↵
cin>>cnt;↵
return cnt;↵
}↵
↵
int main()↵
{↵
int n; cin>>n;↵
int c1 = flip(1,1);↵
if(c1==n)↵
{↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
int c2 = flip(1,1);↵
bool pre = 0; //does previous need a flip?↵
if(c2<c1)↵
{↵
pre=1;↵
}↵
if(c2==n)↵
{↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
int cnt = c2;↵
for(int i = 2; i <= n - 1; i++)↵
{↵
int prevcnt = cnt;↵
int newcnt;↵
if(pre)↵
{↵
newcnt = flip(i-1,i);↵
if(newcnt==prevcnt)↵
{↵
pre=1;↵
}↵
else↵
{↵
pre=0;↵
}↵
}↵
else↵
{↵
newcnt = flip(i,i);↵
if(newcnt<prevcnt)↵
{↵
pre=1;↵
}↵
else↵
{↵
pre=0;↵
}↵
}↵
cnt=newcnt;↵
if(newcnt==n)↵
{↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
}↵
if(cnt==n)↵
{↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
if(cnt==n-2)↵
{↵
flip(n-1,n);↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
assert(cnt==n-1);↵
if(pre)↵
{↵
flip(n-1,n-1);↵
cout<<-1<<'\n'; fflush(stdout);↵
}↵
else ↵
{↵
flip(n,n);↵
cout<<-1<<'\n'; fflush(stdout);↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
### Problem D1↵
↵
First, we can use $18$ moves to determine the value of $a$, by asking $2$ to $19$ in increasing order and the first yes answer will be the value of $a$. If there're no "yes" answers, then the value of $a$ is $20$.↵
↵
Call a number good if it can be represented as the sum of nonnegative multiples of $a$s and $b$. Note that if $x$ is good, then $x + a, x + b$ are both good.↵
↵
Now that we have the value of $a$, let's think about what $b$ is. Consider the numbers $ka + 1, ka + 2, ..., ka + (a - 1)$ for a fixed $k$. If none of these numbers are good, we can immediately say that $b$ is larger than $(k + 1)a$. Why? Suppose $b = qa + r$. Clearly, $r \neq 0$ since $a$ and $b$ are coprime. Note that $xa + r$ for all $x \ge q$ will be the good, since $xa + r = (qa + r) + (x - q)a = b + (x - q)a$. So, $b$ cannot be less than any of the numbers $ka + 1, ka + 2, ..., ka + (a - 1)$, or else one of these numbers would've been good, a contradiction. Note that this also means that if $y$ is the smallest integer such that $ya + 1, ya + 2, ..., ya + (a - 1)$ are not all bad, then there will be exactly one good number, which will be $b$. Also note that for all integers $k > y$, there will have at least one good number among $ka + 1, ka + 2, ..., ka + (a - 1)$. Thus, we can now binary search for the value of $y$. In each iteration of the binary search, we need to ask at most $a - 1 \le 19$ questions, and there are at most $\lceil\log_{2}(500000)\rceil \le 19$ iterations, so the maximum number of operations needed is $19 \cdot 19 + 18 = 379 < 380$. ↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
bool good(int n) //returns whether n can be represented as ax + by↵
{↵
cout<<"? "<<n<<'\n';↵
fflush(stdout);↵
int x; cin>>x;↵
return x;↵
}↵
↵
const int N = 500000;↵
int main()↵
{↵
int a, b;↵
a=20;↵
int t;↵
cin>>t;↵
while(t--)↵
{↵
a=20;↵
for(int i = 2; i <= 19; i++)↵
{↵
if(good(i))↵
{↵
a=i;↵
break;↵
}↵
}↵
int lo = 1; int hi = N/a+2;↵
while(lo<=hi)↵
{↵
int mid = (lo+hi)>>1;↵
int pos = -1;↵
for(int i = 1; i <= a - 1; i++)↵
{↵
if(good(mid*a+i))↵
{↵
pos=mid*a+i;↵
break;↵
}↵
}↵
if(pos==-1)↵
{↵
lo=mid+1;↵
}↵
else↵
{↵
b=pos;↵
hi=mid-1;↵
}↵
}↵
cout<<"! "<<a<<' '<<b<<'\n';↵
fflush(stdout);↵
//int x; cin>>x;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
### Problem D2↵
↵
This problem is the same as D1, but with higher constraints. Firstly, we find the value of $a$ in $18$ moves as in problem D. To proceed, we need to think about this problem from another angle. Suppose we know a number $N$ that is good and not a multiple of $a$, and we can find the maximum number $k$ such that $N - ka$ is good, then what does this tell us? This means that $N - ka$ is a multiple of $b$. Why? We know that $N - ka = ax + by$ for some nonnegative integers $x$ and $y$ since $N - ka$ is good. If $x > 0$, then $N - (k + 1)a = a(x - 1) + by$ is also good, contradicting the maximality of $k$. Thus, $x = 0$ and so $N - ka = by$. Note that $b > 0$ since we choose $N$ so that it's not a multiple of $a$.↵
↵
To find a value of $N$ such that $N$ is good and not a multiple of $a$, it is sufficient to take $500000a - 1$, since any number greater than $ab - a - b$ is guaranteed to be good. (this is a well-known fact)↵
↵
We can find the largest $k$ such that $N - ka$ is good via binary search, because if $N - ma$ is not good then $N - (m + 1)a$ can't be good. (or else if $N - (m + 1)a = ax + by$, then $N - ma = a(x + 1) + by$) This takes at most $19$ questions.↵
↵
What to do after finding a value which is a multiple of $b$? Let $C = N - ka$. We consider the prime factorization of $C$. The main claim is that if $x \mid C$ is good, then $x$ must be a multiple of $b$. The reasoning is the same as what we did before. So, we can find the prime factorization of $C$, and divide the prime factors one by one. If the number becomes bad, we know that the prime factor cannot be removed, and proceed to the next prime factor. Since a number less than $510000000$ can have at most $1823$ prime factors (maximum is $2^{1823}$), so this takes another $1823$ questions.↵
↵
Thus, we only used$18 + 19 + 18 = 55 <at most $18 + 19 + 23 = 60$ questions to find the values of $a$ and $b$.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
bool good(int n) //returns whether n can be represented as ax + by↵
{↵
cout<<"? "<<n<<'\n';↵
fflush(stdout);↵
int x; cin>>x;↵
return x;↵
}↵
↵
struct NumberTheory↵
{↵
vector<ll> primes;↵
vector<bool> prime;↵
vector<ll> totient;↵
vector<ll> sumdiv;↵
vector<ll> bigdiv;↵
void Sieve(ll n)↵
{↵
prime.assign(n+1, 1);↵
prime[1] = false;↵
for(ll i = 2; i <= n; i++)↵
{↵
if(prime[i])↵
{↵
primes.pb(i);↵
for(ll j = i*2; j <= n; j += i)↵
{↵
prime[j] = false;↵
}↵
}↵
}↵
}↵
↵
ll phi(ll x)↵
{↵
map<ll,ll> pf;↵
ll num = 1; ll num2 = x;↵
for(ll i = 0; primes[i]*primes[i] <= x; i++)↵
{↵
if(x%primes[i]==0)↵
{↵
num2/=primes[i];↵
num*=(primes[i]-1);↵
}↵
while(x%primes[i]==0)↵
{↵
x/=primes[i];↵
pf[primes[i]]++;↵
}↵
}↵
if(x>1)↵
{↵
pf[x]++; num2/=x; num*=(x-1);↵
}↵
x = 1;↵
num*=num2;↵
return num;↵
}↵
↵
bool isprime(ll x)↵
{↵
if(x==1) return false;↵
for(ll i = 0; primes[i]*primes[i] <= x; i++)↵
{↵
if(x%primes[i]==0) return false;↵
}↵
return true;↵
}↵
↵
void SievePhi(ll n)↵
{↵
totient.resize(n+1);↵
for (int i = 1; i <= n; ++i) totient[i] = i;↵
for (int i = 2; i <= n; ++i)↵
{↵
if (totient[i] == i)↵
{↵
for (int j = i; j <= n; j += i)↵
{↵
totient[j] -= totient[j] / i;↵
}↵
}↵
}↵
}↵
↵
void SieveSumDiv(ll n)↵
{↵
sumdiv.resize(n+1);↵
for(int i = 1; i <= n; ++i)↵
{↵
for(int j = i; j <= n; j += i)↵
{↵
sumdiv[j] += i;↵
}↵
}↵
}↵
↵
ll getPhi(ll n)↵
{↵
return totient[n];↵
}↵
↵
ll getSumDiv(ll n)↵
{↵
return sumdiv[n];↵
}↵
↵
ll modpow(ll a, ll b, ll mod)↵
{↵
ll r = 1;↵
if(b < 0) b += mod*100000LL;↵
while(b)↵
{↵
if(b&1) r = (r*a)%mod;↵
a = (a*a)%mod;↵
b>>=1;↵
}↵
return r;↵
}↵
↵
ll inv(ll a, ll mod)↵
{↵
return modpow(a, mod - 2, mod);↵
}↵
↵
ll invgeneral(ll a, ll mod)↵
{↵
ll ph = phi(mod);↵
ph--;↵
return modpow(a, ph, mod);↵
}↵
↵
void getpf(vector<ii>& pf, ll n)↵
{↵
for(ll i = 0; primes[i]*primes[i] <= n; i++)↵
{↵
int cnt = 0;↵
while(n%primes[i]==0)↵
{↵
n/=primes[i]; cnt++;↵
}↵
pf.pb(ii(primes[i], cnt));↵
}↵
if(n>1)↵
{↵
pf.pb(ii(n, 1));↵
}↵
}↵
↵
//ll op;↵
void getDiv(vector<ll>& div, vector<ii>& pf, ll n, int i)↵
{↵
//op++;↵
ll x, k;↵
if(i >= pf.size()) return ;↵
x = n;↵
for(k = 0; k <= pf[i].se; k++)↵
{↵
if(i==int(pf.size())-1) div.pb(x);↵
getDiv(div, pf, x, i + 1);↵
x *= pf[i].fi;↵
}↵
}↵
};↵
↵
NumberTheory nt;↵
↵
const int N = 500000;↵
int main()↵
{↵
nt.Sieve(N+1);↵
int a, b;↵
a=20;↵
int t; cin>>t;↵
while(t--)↵
{↵
a=20;↵
for(int i = 2; i <= 19; i++)↵
{↵
if(good(i))↵
{↵
a=i;↵
break;↵
}↵
}↵
int MX = N*a-1;↵
int lo = 1; int hi = N-1;↵
int ans = 0;↵
while(lo<=hi)↵
{↵
int mid=(lo+hi)>>1;↵
if(good(MX-mid*a))↵
{↵
ans=mid;↵
lo=mid+1;↵
}↵
else↵
{↵
hi=mid-1;↵
}↵
}↵
int big = MX - ans*a; //this thing is a multiple of b↵
vector<ii> ppf;↵
nt.getpf(ppf, big);↵
for(int i = 0; i < ppf.size(); i++)↵
{↵
int p = ppf[i].fi;↵
while(big%p==0)↵
{↵
if(!good(big/p)) break;↵
big/=p;↵
}↵
}↵
b=big;↵
cout<<"! "<<a<<' '<<b<<'\n';↵
fflush(stdout);↵
//int x; cin>>x;↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### Problem E↵
↵
Firstly, note that a connected graph on $n$ vertices with $n$ edges contains exactly $1$ cycle. Call the vertices on the cycle the cycle vertices. From each cycle vertex, there's a tree rooted at it. Thus, call the remaining vertices the tree vertices. Note that the number of useless edges is equal to the length of the cycle.↵
↵
Now, we do some casework :↵
↵
- $u$ is equal to a tree vertex↵
↵
Note that this will not change the length of the cycle. Thus, we just have to count how many ways are there to change the value of $a_{u}$ such that the graph remains connected. The observation is that for each tree node $u$, the only possible values of $a_{u}$ are the nodes which are not in the subtree of $u$ in the tree $u$ belongs to. Thus, the number of possibilities can be calculated with a tree dp. For each tree, we calculate the subtree size of each node and add all these subtree sizes and subtract this from the total number of ways to choose a non-tree vertex $u$ and choosing the value of $a_{u}$. This part can be done in $O(n)$ time.↵
↵
- $u$ is equal to a cycle vertex↵
↵
For two cycle vertices $u$ and $v$, let $d(u, v)$ be the directed distance from $u$ to $v$ (We consider the distance from $u$ to $v$ in the functional graph $i \rightarrow a_{i}$ for all $1 \le i \le n$). Note that if we change $a_{u}$ to $x$, and the root of the tree $x$ is in is $v$ ($x = v$ is $x$ is a cycle vertex), then the length of the cycle after the change will be $d(v, u) + 1 + h[x]$, where $h[x]$ is the height of $x$ in its tree. The key is instead of fixing $u$ and iterate through all other nodes $x$, we iterate through all endpoints $x$ and see how it changes our answer. Note that if $x$ is fixed, which also means that $v$ is fixed, then we just have to add $1$ to the answer for $c = d(v, u) + 1 + h[x]$ for all cycle vertices $u$. However, note that $d(v, u)$ ranges from $0$ to $C - 1$ (where $C$ denotes the length of the original cycle), so this is equivalent to adding $1$ to the answer for $c = h[x] + 1, h[x] + 2, ..., h[x] + C$. Now, we can iterate through all vertices $x$ and add $1$ to the answer for $c = h[x] + 1, h[x] + 2, ..., h[x] + C$. To do this quickly, we can employ the "+1, -1" method. Whenever we want to add $1$ to a range $[l, r]$, we add $1$ to $ans_{l}$ and subtract $1$ from $ans_{r + 1}$. Then, to find the actual values of the $ans$ array, we just have to take the prefix sum of the $ans$ array.↵
↵
Finally, do not forget to subtract the cases where $v = a_{u}$ from the answer. The total complexity is $O(n)$.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int N = 1000011;↵
↵
bool iscycle[N];↵
int visited[N];↵
ll ans[N];↵
int n;↵
vi adj[N];↵
int a[N];↵
vi cyc;↵
ll subsize[N];↵
vector<vector<ll> > vec; //nodes sorted by height↵
ll subsizesum;↵
↵
void dfs2(int u)↵
{↵
cyc.pb(u);↵
iscycle[u]=1;↵
visited[u] = 3;↵
if(visited[a[u]] == 3) return ;↵
dfs2(a[u]);↵
}↵
↵
void findcyc(int u)↵
{↵
visited[u] = 2;↵
if(visited[a[u]] == 0)↵
{↵
findcyc(a[u]);↵
}↵
else if(visited[a[u]] == 1)↵
{↵
visited[u] = 1;↵
return ;↵
}↵
else↵
{↵
dfs2(u);↵
}↵
visited[u] = 1;↵
}↵
↵
void upd(int l, int r, ll s)↵
{↵
ans[r+1]-=s;↵
ans[l]+=s;↵
}↵
↵
int ptr;↵
void dfs(int u, int d)↵
{↵
if(vec[ptr].size()<=d) vec[ptr].pb(0);↵
vec[ptr][d]++;↵
subsize[u]=1;↵
for(int i = 0; i < adj[u].size(); i++)↵
{↵
int v = adj[u][i];↵
dfs(v,d+1);↵
subsize[u]+=subsize[v];↵
}↵
if(d>0) subsizesum+=subsize[u];↵
}↵
↵
int main()↵
{↵
//ios_base::sync_with_stdio(0); cin.tie(0);↵
scanf("%d", &n);↵
for(int i = 0; i < n; i++)↵
{↵
//cin>>a[i];↵
scanf("%d", a + i);↵
a[i]--;↵
}↵
findcyc(0);↵
memset(visited,0,sizeof(visited));↵
for(int i = 0; i < n; i++)↵
{↵
if(!(iscycle[a[i]]&&iscycle[i]))↵
{↵
adj[a[i]].pb(i);↵
}↵
}↵
vec.resize(int(cyc.size()));↵
int c = cyc.size();↵
for(int i = 0; i < cyc.size(); i++)↵
{↵
dfs(cyc[i],0);↵
ptr++;↵
}↵
upd(c,c,ll(n-1)*ll(n-c) - subsizesum);↵
for(int i = 0; i < c; i++)↵
{↵
for(int j = 0; j < vec[i].size(); j++)↵
{↵
//j is the height↵
upd(j+1,j+c,vec[i][j]);↵
}↵
}↵
upd(c,c,-c); //subtract original cycle edges↵
ll cur=0;↵
for(int i = 1; i <= n; i++)↵
{↵
cur+=ans[i];↵
printf("%I64d ", cur);↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
1. [user:W4yneb0t,2017-01-20] (perfect score in < 1 hour!)↵
↵
2. [user:aaaaajack,2017-01-20] (perfect score)↵
↵
3. [user:eddy1021,2017-01-20]↵
↵
Here is the editorial :↵
↵
### Problem A ↵
↵
This problem can be solved by greedy. We list down the positive integers one by one. We keep a pointer that initially points to the first letter of $s$. Whenever the pointed character in the string $s$ matches the corresponding digit of the integer, we move the pointer one step to the right and continue. Repeat this process until the pointer reaches the end. ↵
↵
However, we still need to know whether the answer can be large. The key is to note that the answer will never exceed $10^{6}$, because after writing down $10$ consecutive numbers, at least one of them has last digit equals to the current digit, so the pointer will move to the right at least once when we write down $10$ consecutive numbers. Thus, in the worse case, we'll only list down the numbers from $1$ to $10^{6}$, which is definitely fast enough.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
vector<pair<char,int> > vec;↵
const int N = 100000;↵
↵
void gen()↵
{↵
for(int i = 1; i <= N*10; i++)↵
{↵
int x=i;↵
string r;↵
while(x)↵
{↵
r+=char('0'+x%10);↵
x/=10;↵
}↵
for(int j = int(r.size())-1;j>=0;j--)↵
{↵
vec.pb(mp(r[j],i));↵
} ↵
}↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
gen();↵
string s; cin>>s;↵
int ptr=0; int p2 = 0;↵
while(p2<s.length()&&ptr<vec.size())↵
{↵
if(s[p2]==vec[ptr].fi) ↵
{↵
p2++;↵
ptr++;↵
continue;↵
}↵
ptr++;↵
}↵
ptr--; //remember this↵
cout<<vec[ptr].se;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
### Problem B↵
↵
This problem can be solved using dynamic programming. Firstly, observe that if we already determine which set of problems to solve, then it's best to solve the problem in increasing order of time needed to solve in order to minimize the time penalty. Thus, we can first sort the problems in increasing order of time needed, breaking ties arbitarily.↵
↵
Let $dp[i][j]$ denote the maximum number of problems solved and minimum time penalty acquired when doing so by using exactly $j$ minutes and only solving problems among the first $i$ ones. $dp[0][0] = (0, 0)$ (the first integer denotes the number of problems solved and the second integer denotes the time penalty in order to do so). The transitions can be handled easily by simply considering whether to solve the $i$-th problem or not. The time complexity of this solution is $O(nT)$ ($T$ is the duration of the contest)↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
const int N = 100011;↵
const int T = 301;↵
ii dp[N][T];↵
ii a[N];↵
↵
ii maxi(ii a, ii b)↵
{↵
if(a.fi!=b.fi)↵
{↵
if(a.fi>b.fi) return a;↵
else return b;↵
}↵
else↵
{↵
if(a.se<b.se) return a;↵
else return b;↵
}↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
int n; cin>>n;↵
int t = 300;↵
for(int i = 1; i <= n; i++)↵
{↵
cin>>a[i].fi>>a[i].se;↵
}↵
sort(a+1,a+n+1);↵
for(int i = 0; i <= n; i++)↵
{↵
for(int j = 0; j <= t; j++)↵
{↵
dp[i][j]=mp(-1,-1);↵
}↵
}↵
dp[0][0] = mp(0,0);↵
ii maxans = mp(0,0);↵
for(int i = 1; i <= n; i++)↵
{↵
for(int j = 0; j <= 300; j++)↵
{↵
dp[i][j] = dp[i-1][j];↵
if(j-a[i].fi>=0&&dp[i-1][j-a[i].fi].fi!=-1)↵
{↵
dp[i][j] = maxi(dp[i][j], mp(dp[i-1][j-a[i].fi].fi+1, dp[i-1][j-a[i].fi].se+j+20LL*a[i].se));↵
}↵
if(i==n) maxans = maxi(maxans, dp[i][j]);↵
}↵
}↵
cout<<maxans.fi<<' '<<maxans.se<<'\n';↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### Problem C↵
↵
This is an ad hoc problem. Firstly, we can use two moves to determine what the value of the first bit is. (simply flipping it twice will tell you its value. Now, if the bit is $1$, you don't need to flip it anymore. If it's $0$, you'll need to flip it. In any case, we'll flip the second bit as well. (if the first bit needs to be flipped, we'll flip $[1, 2]$ and flip $[2, 2]$ otherwise) After flipping the second bit, we can determine whether it's a $1$ or $0$ by calculating from the total number of $1$s of the string before the flip and after the flip. We can repeat this for every $2$ consecutive bits until we arrive at the last two bits. At this point, we know what the second last bit is, and we also know the total number of $1$ bits. So, we can easily deduce the value of the last bit from the information as well. Now, we just need to perform one last flip to make the last $2$ bits become $1$. The total number of moves made is $n + 1$.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
int flip(int l, int r)↵
{↵
cout<<l<<' '<<r<<'\n';↵
fflush(stdout);↵
int cnt; ↵
cin>>cnt;↵
return cnt;↵
}↵
↵
int main()↵
{↵
int n; cin>>n;↵
int c1 = flip(1,1);↵
if(c1==n)↵
{↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
int c2 = flip(1,1);↵
bool pre = 0; //does previous need a flip?↵
if(c2<c1)↵
{↵
pre=1;↵
}↵
if(c2==n)↵
{↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
int cnt = c2;↵
for(int i = 2; i <= n - 1; i++)↵
{↵
int prevcnt = cnt;↵
int newcnt;↵
if(pre)↵
{↵
newcnt = flip(i-1,i);↵
if(newcnt==prevcnt)↵
{↵
pre=1;↵
}↵
else↵
{↵
pre=0;↵
}↵
}↵
else↵
{↵
newcnt = flip(i,i);↵
if(newcnt<prevcnt)↵
{↵
pre=1;↵
}↵
else↵
{↵
pre=0;↵
}↵
}↵
cnt=newcnt;↵
if(newcnt==n)↵
{↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
}↵
if(cnt==n)↵
{↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
if(cnt==n-2)↵
{↵
flip(n-1,n);↵
cout<<-1<<'\n'; fflush(stdout);↵
return 0;↵
}↵
assert(cnt==n-1);↵
if(pre)↵
{↵
flip(n-1,n-1);↵
cout<<-1<<'\n'; fflush(stdout);↵
}↵
else ↵
{↵
flip(n,n);↵
cout<<-1<<'\n'; fflush(stdout);↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
### Problem D1↵
↵
First, we can use $18$ moves to determine the value of $a$, by asking $2$ to $19$ in increasing order and the first yes answer will be the value of $a$. If there're no "yes" answers, then the value of $a$ is $20$.↵
↵
Call a number good if it can be represented as the sum of nonnegative multiples of $a$s and $b$. Note that if $x$ is good, then $x + a, x + b$ are both good.↵
↵
Now that we have the value of $a$, let's think about what $b$ is. Consider the numbers $ka + 1, ka + 2, ..., ka + (a - 1)$ for a fixed $k$. If none of these numbers are good, we can immediately say that $b$ is larger than $(k + 1)a$. Why? Suppose $b = qa + r$. Clearly, $r \neq 0$ since $a$ and $b$ are coprime. Note that $xa + r$ for all $x \ge q$ will be the good, since $xa + r = (qa + r) + (x - q)a = b + (x - q)a$. So, $b$ cannot be less than any of the numbers $ka + 1, ka + 2, ..., ka + (a - 1)$, or else one of these numbers would've been good, a contradiction. Note that this also means that if $y$ is the smallest integer such that $ya + 1, ya + 2, ..., ya + (a - 1)$ are not all bad, then there will be exactly one good number, which will be $b$. Also note that for all integers $k > y$, there will have at least one good number among $ka + 1, ka + 2, ..., ka + (a - 1)$. Thus, we can now binary search for the value of $y$. In each iteration of the binary search, we need to ask at most $a - 1 \le 19$ questions, and there are at most $\lceil\log_{2}(500000)\rceil \le 19$ iterations, so the maximum number of operations needed is $19 \cdot 19 + 18 = 379 < 380$. ↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
bool good(int n) //returns whether n can be represented as ax + by↵
{↵
cout<<"? "<<n<<'\n';↵
fflush(stdout);↵
int x; cin>>x;↵
return x;↵
}↵
↵
const int N = 500000;↵
int main()↵
{↵
int a, b;↵
a=20;↵
int t;↵
cin>>t;↵
while(t--)↵
{↵
a=20;↵
for(int i = 2; i <= 19; i++)↵
{↵
if(good(i))↵
{↵
a=i;↵
break;↵
}↵
}↵
int lo = 1; int hi = N/a+2;↵
while(lo<=hi)↵
{↵
int mid = (lo+hi)>>1;↵
int pos = -1;↵
for(int i = 1; i <= a - 1; i++)↵
{↵
if(good(mid*a+i))↵
{↵
pos=mid*a+i;↵
break;↵
}↵
}↵
if(pos==-1)↵
{↵
lo=mid+1;↵
}↵
else↵
{↵
b=pos;↵
hi=mid-1;↵
}↵
}↵
cout<<"! "<<a<<' '<<b<<'\n';↵
fflush(stdout);↵
//int x; cin>>x;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
### Problem D2↵
↵
This problem is the same as D1, but with higher constraints. Firstly, we find the value of $a$ in $18$ moves as in problem D. To proceed, we need to think about this problem from another angle. Suppose we know a number $N$ that is good and not a multiple of $a$, and we can find the maximum number $k$ such that $N - ka$ is good, then what does this tell us? This means that $N - ka$ is a multiple of $b$. Why? We know that $N - ka = ax + by$ for some nonnegative integers $x$ and $y$ since $N - ka$ is good. If $x > 0$, then $N - (k + 1)a = a(x - 1) + by$ is also good, contradicting the maximality of $k$. Thus, $x = 0$ and so $N - ka = by$. Note that $b > 0$ since we choose $N$ so that it's not a multiple of $a$.↵
↵
To find a value of $N$ such that $N$ is good and not a multiple of $a$, it is sufficient to take $500000a - 1$, since any number greater than $ab - a - b$ is guaranteed to be good. (this is a well-known fact)↵
↵
We can find the largest $k$ such that $N - ka$ is good via binary search, because if $N - ma$ is not good then $N - (m + 1)a$ can't be good. (or else if $N - (m + 1)a = ax + by$, then $N - ma = a(x + 1) + by$) This takes at most $19$ questions.↵
↵
What to do after finding a value which is a multiple of $b$? Let $C = N - ka$. We consider the prime factorization of $C$. The main claim is that if $x \mid C$ is good, then $x$ must be a multiple of $b$. The reasoning is the same as what we did before. So, we can find the prime factorization of $C$, and divide the prime factors one by one. If the number becomes bad, we know that the prime factor cannot be removed, and proceed to the next prime factor. Since a number less than $
↵
Thus, we only used
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
bool good(int n) //returns whether n can be represented as ax + by↵
{↵
cout<<"? "<<n<<'\n';↵
fflush(stdout);↵
int x; cin>>x;↵
return x;↵
}↵
↵
struct NumberTheory↵
{↵
vector<ll> primes;↵
vector<bool> prime;↵
vector<ll> totient;↵
vector<ll> sumdiv;↵
vector<ll> bigdiv;↵
void Sieve(ll n)↵
{↵
prime.assign(n+1, 1);↵
prime[1] = false;↵
for(ll i = 2; i <= n; i++)↵
{↵
if(prime[i])↵
{↵
primes.pb(i);↵
for(ll j = i*2; j <= n; j += i)↵
{↵
prime[j] = false;↵
}↵
}↵
}↵
}↵
↵
ll phi(ll x)↵
{↵
map<ll,ll> pf;↵
ll num = 1; ll num2 = x;↵
for(ll i = 0; primes[i]*primes[i] <= x; i++)↵
{↵
if(x%primes[i]==0)↵
{↵
num2/=primes[i];↵
num*=(primes[i]-1);↵
}↵
while(x%primes[i]==0)↵
{↵
x/=primes[i];↵
pf[primes[i]]++;↵
}↵
}↵
if(x>1)↵
{↵
pf[x]++; num2/=x; num*=(x-1);↵
}↵
x = 1;↵
num*=num2;↵
return num;↵
}↵
↵
bool isprime(ll x)↵
{↵
if(x==1) return false;↵
for(ll i = 0; primes[i]*primes[i] <= x; i++)↵
{↵
if(x%primes[i]==0) return false;↵
}↵
return true;↵
}↵
↵
void SievePhi(ll n)↵
{↵
totient.resize(n+1);↵
for (int i = 1; i <= n; ++i) totient[i] = i;↵
for (int i = 2; i <= n; ++i)↵
{↵
if (totient[i] == i)↵
{↵
for (int j = i; j <= n; j += i)↵
{↵
totient[j] -= totient[j] / i;↵
}↵
}↵
}↵
}↵
↵
void SieveSumDiv(ll n)↵
{↵
sumdiv.resize(n+1);↵
for(int i = 1; i <= n; ++i)↵
{↵
for(int j = i; j <= n; j += i)↵
{↵
sumdiv[j] += i;↵
}↵
}↵
}↵
↵
ll getPhi(ll n)↵
{↵
return totient[n];↵
}↵
↵
ll getSumDiv(ll n)↵
{↵
return sumdiv[n];↵
}↵
↵
ll modpow(ll a, ll b, ll mod)↵
{↵
ll r = 1;↵
if(b < 0) b += mod*100000LL;↵
while(b)↵
{↵
if(b&1) r = (r*a)%mod;↵
a = (a*a)%mod;↵
b>>=1;↵
}↵
return r;↵
}↵
↵
ll inv(ll a, ll mod)↵
{↵
return modpow(a, mod - 2, mod);↵
}↵
↵
ll invgeneral(ll a, ll mod)↵
{↵
ll ph = phi(mod);↵
ph--;↵
return modpow(a, ph, mod);↵
}↵
↵
void getpf(vector<ii>& pf, ll n)↵
{↵
for(ll i = 0; primes[i]*primes[i] <= n; i++)↵
{↵
int cnt = 0;↵
while(n%primes[i]==0)↵
{↵
n/=primes[i]; cnt++;↵
}↵
pf.pb(ii(primes[i], cnt));↵
}↵
if(n>1)↵
{↵
pf.pb(ii(n, 1));↵
}↵
}↵
↵
//ll op;↵
void getDiv(vector<ll>& div, vector<ii>& pf, ll n, int i)↵
{↵
//op++;↵
ll x, k;↵
if(i >= pf.size()) return ;↵
x = n;↵
for(k = 0; k <= pf[i].se; k++)↵
{↵
if(i==int(pf.size())-1) div.pb(x);↵
getDiv(div, pf, x, i + 1);↵
x *= pf[i].fi;↵
}↵
}↵
};↵
↵
NumberTheory nt;↵
↵
const int N = 500000;↵
int main()↵
{↵
nt.Sieve(N+1);↵
int a, b;↵
a=20;↵
int t; cin>>t;↵
while(t--)↵
{↵
a=20;↵
for(int i = 2; i <= 19; i++)↵
{↵
if(good(i))↵
{↵
a=i;↵
break;↵
}↵
}↵
int MX = N*a-1;↵
int lo = 1; int hi = N-1;↵
int ans = 0;↵
while(lo<=hi)↵
{↵
int mid=(lo+hi)>>1;↵
if(good(MX-mid*a))↵
{↵
ans=mid;↵
lo=mid+1;↵
}↵
else↵
{↵
hi=mid-1;↵
}↵
}↵
int big = MX - ans*a; //this thing is a multiple of b↵
vector<ii> ppf;↵
nt.getpf(ppf, big);↵
for(int i = 0; i < ppf.size(); i++)↵
{↵
int p = ppf[i].fi;↵
while(big%p==0)↵
{↵
if(!good(big/p)) break;↵
big/=p;↵
}↵
}↵
b=big;↵
cout<<"! "<<a<<' '<<b<<'\n';↵
fflush(stdout);↵
//int x; cin>>x;↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### Problem E↵
↵
Firstly, note that a connected graph on $n$ vertices with $n$ edges contains exactly $1$ cycle. Call the vertices on the cycle the cycle vertices. From each cycle vertex, there's a tree rooted at it. Thus, call the remaining vertices the tree vertices. Note that the number of useless edges is equal to the length of the cycle.↵
↵
Now, we do some casework :↵
↵
- $u$ is equal to a tree vertex↵
↵
Note that this will not change the length of the cycle. Thus, we just have to count how many ways are there to change the value of $a_{u}$ such that the graph remains connected. The observation is that for each tree node $u$, the only possible values of $a_{u}$ are the nodes which are not in the subtree of $u$ in the tree $u$ belongs to. Thus, the number of possibilities can be calculated with a tree dp. For each tree, we calculate the subtree size of each node and add all these subtree sizes and subtract this from the total number of ways to choose a non-tree vertex $u$ and choosing the value of $a_{u}$. This part can be done in $O(n)$ time.↵
↵
- $u$ is equal to a cycle vertex↵
↵
For two cycle vertices $u$ and $v$, let $d(u, v)$ be the directed distance from $u$ to $v$ (We consider the distance from $u$ to $v$ in the functional graph $i \rightarrow a_{i}$ for all $1 \le i \le n$). Note that if we change $a_{u}$ to $x$, and the root of the tree $x$ is in is $v$ ($x = v$ is $x$ is a cycle vertex), then the length of the cycle after the change will be $d(v, u) + 1 + h[x]$, where $h[x]$ is the height of $x$ in its tree. The key is instead of fixing $u$ and iterate through all other nodes $x$, we iterate through all endpoints $x$ and see how it changes our answer. Note that if $x$ is fixed, which also means that $v$ is fixed, then we just have to add $1$ to the answer for $c = d(v, u) + 1 + h[x]$ for all cycle vertices $u$. However, note that $d(v, u)$ ranges from $0$ to $C - 1$ (where $C$ denotes the length of the original cycle), so this is equivalent to adding $1$ to the answer for $c = h[x] + 1, h[x] + 2, ..., h[x] + C$. Now, we can iterate through all vertices $x$ and add $1$ to the answer for $c = h[x] + 1, h[x] + 2, ..., h[x] + C$. To do this quickly, we can employ the "+1, -1" method. Whenever we want to add $1$ to a range $[l, r]$, we add $1$ to $ans_{l}$ and subtract $1$ from $ans_{r + 1}$. Then, to find the actual values of the $ans$ array, we just have to take the prefix sum of the $ans$ array.↵
↵
Finally, do not forget to subtract the cases where $v = a_{u}$ from the answer. The total complexity is $O(n)$.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
↵
#define fi first↵
#define se second↵
#define mp make_pair↵
#define pb push_back↵
#define fbo find_by_order↵
#define ook order_of_key↵
↵
typedef long long ll;↵
typedef pair<ll,ll> ii;↵
typedef vector<int> vi;↵
typedef long double ld; ↵
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;↵
typedef set<int>::iterator sit;↵
typedef map<int,int>::iterator mit;↵
typedef vector<int>::iterator vit;↵
↵
const int N = 1000011;↵
↵
bool iscycle[N];↵
int visited[N];↵
ll ans[N];↵
int n;↵
vi adj[N];↵
int a[N];↵
vi cyc;↵
ll subsize[N];↵
vector<vector<ll> > vec; //nodes sorted by height↵
ll subsizesum;↵
↵
void dfs2(int u)↵
{↵
cyc.pb(u);↵
iscycle[u]=1;↵
visited[u] = 3;↵
if(visited[a[u]] == 3) return ;↵
dfs2(a[u]);↵
}↵
↵
void findcyc(int u)↵
{↵
visited[u] = 2;↵
if(visited[a[u]] == 0)↵
{↵
findcyc(a[u]);↵
}↵
else if(visited[a[u]] == 1)↵
{↵
visited[u] = 1;↵
return ;↵
}↵
else↵
{↵
dfs2(u);↵
}↵
visited[u] = 1;↵
}↵
↵
void upd(int l, int r, ll s)↵
{↵
ans[r+1]-=s;↵
ans[l]+=s;↵
}↵
↵
int ptr;↵
void dfs(int u, int d)↵
{↵
if(vec[ptr].size()<=d) vec[ptr].pb(0);↵
vec[ptr][d]++;↵
subsize[u]=1;↵
for(int i = 0; i < adj[u].size(); i++)↵
{↵
int v = adj[u][i];↵
dfs(v,d+1);↵
subsize[u]+=subsize[v];↵
}↵
if(d>0) subsizesum+=subsize[u];↵
}↵
↵
int main()↵
{↵
//ios_base::sync_with_stdio(0); cin.tie(0);↵
scanf("%d", &n);↵
for(int i = 0; i < n; i++)↵
{↵
//cin>>a[i];↵
scanf("%d", a + i);↵
a[i]--;↵
}↵
findcyc(0);↵
memset(visited,0,sizeof(visited));↵
for(int i = 0; i < n; i++)↵
{↵
if(!(iscycle[a[i]]&&iscycle[i]))↵
{↵
adj[a[i]].pb(i);↵
}↵
}↵
vec.resize(int(cyc.size()));↵
int c = cyc.size();↵
for(int i = 0; i < cyc.size(); i++)↵
{↵
dfs(cyc[i],0);↵
ptr++;↵
}↵
upd(c,c,ll(n-1)*ll(n-c) - subsizesum);↵
for(int i = 0; i < c; i++)↵
{↵
for(int j = 0; j < vec[i].size(); j++)↵
{↵
//j is the height↵
upd(j+1,j+c,vec[i][j]);↵
}↵
}↵
upd(c,c,-c); //subtract original cycle edges↵
ll cur=0;↵
for(int i = 1; i <= n; i++)↵
{↵
cur+=ans[i];↵
printf("%I64d ", cur);↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
