Submission #1016244

#TimeUsernameProblemLanguageResultExecution timeMemory
1016244MarwenElarbiSeptember (APIO24_september)C++17
0 / 100
1 ms3420 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define se second #define fi first const int nax=1e5+5; vector<int> adj[nax]; pair<int,int> tab[nax]; void dfs(int x,int p){ for(auto u:adj[x]){ if(u==p) continue; dfs(u,x); tab[x].se=max(tab[x].se,tab[u].se); } return; } int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) { for (int i = 0; i <= N; ++i) { adj[i].clear(); tab[i]={1e9,-1e9}; } for (int i = 1; i < N; ++i) { adj[F[i]].pb(i+1); adj[i+1].pb(F[i]); } for (int i = 0; i < M; ++i) { for (int j = 0; j < N-1; ++j) { tab[S[i][j]].fi=min(tab[S[i][j]].fi,j); tab[S[i][j]].se=max(tab[S[i][j]].se,j); } } dfs(0,-1); vector<pair<int,int>> v; for (int i = 1; i < N; ++i) { v.pb({tab[i].fi,0}); v.pb({tab[i].se,1}); } sort(v.begin(),v.end()); int cnt=0; int ans=0; for (int i = 0; i < (int)v.size(); ++i) { if(v[i].se==0) cnt++; else cnt--; if(cnt==0) ans++; } return ans; } /* void taskcase() { int N, M; assert(2 == scanf("%d%d", &N, &M)); std::vector<int> F(N); F[0] = -1; for (int i = 1; i < N; ++i) assert(1 == scanf("%d", &F[i])); std::vector<std::vector<int>> S(M, std::vector<int>(N - 1)); for (int i = 0; i < M; ++i) for (int j = 0; j < N - 1; ++j) assert(1 == scanf("%d", &S[i][j])); printf("%d\n", solve(N, M, F, S)); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int T; assert(1 == scanf("%d", &T)); while(T--) taskcase(); return 0; } */
#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...