Submission #1008825

#TimeUsernameProblemLanguageResultExecution timeMemory
1008825Math4Life2020September (APIO24_september)C++17
100 / 100
102 ms14772 KiB
// 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)

september.cpp: In function 'int solve(int, int, std::vector<int>, std::vector<std::vector<int> >)':
september.cpp:63:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (ll i=0;i<(stops.size()-1);i++) {
      |              ~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...