# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1008825 | Math4Life2020 | September (APIO24_september) | C++17 | 102 ms | 14772 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using lll = __int128;
const lll p1 = 144403552893599;
const lll a1 = 981372590237;
const lll p2 = 270969106631203;
const lll a2 = 898374183250;
int solve(int N, int M, vector<int> F, vector<vector<int>> S1) {
vector<vector<int>> S = S1;
for (ll i=0;i<M;i++) {
S[i].push_back(0);
}
vector<lll> hsh1,hsh2;
for (ll i=0;i<M;i++) {
hsh1.push_back(1);
hsh2.push_back(1);
}
vector<ll> stops;
stops.push_back(0);
for (ll i=0;i<N;i++) {
for (ll j=0;j<M;j++) {
hsh1[j]=(hsh1[j]*(a1+S[j][i]))%p1;
hsh2[j]=(hsh2[j]*(a2+S[j][i]))%p2;
}
bool split = true;
for (ll j=0;j<M;j++) {
split = split && (hsh1[j]==hsh1[0]) && (hsh2[j]==hsh2[0]);
}
if (split) {
stops.push_back(i+1);
for (ll j=0;j<M;j++) {
hsh1[j]=1;
hsh2[j]=1;
}
}
}
//cout << "nstops: "<<stops.size()-1<<"\n";
ll kv[N];
ll kind = 0;
ll delactive[N];
for (ll i=0;i<N;i++) {
delactive[i]=0;
if (stops[kind+1]<=i) {
kind++;
}
kv[S[0][i]]=kind;
}
for (ll i=1;i<N;i++) {
ll x = kv[i]; ll y = kv[F[i]]; //y: parent of x -> if y before x (y<x), then issues
if (y<x) {
delactive[y]++;
delactive[x]--;
//cout << "+ at "<<y<<", - at "<<x<<"\n";
}
}
ll nact = 0;
ll ans = 0;
for (ll i=0;i<(stops.size()-1);i++) {
nact += delactive[i];
if (nact == 0) {
ans++;
}
}
return (ans-1);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |