제출 #1062575

#제출 시각아이디문제언어결과실행 시간메모리
1062575alexdd9월 (APIO24_september)C++17
100 / 100
133 ms24784 KiB
#include "september.h" #include <bits/stdc++.h> using namespace std; const int INF = 1e9; vector<int> con[100005]; int mint[100005],maxt[100005]; int submin[100005],submax[100005]; int mars[100005]; void same_day(int le, int ri) { if(le>=ri) return; //cout<<le<<" "<<ri<<" same day\n"; mars[le+1]++; mars[ri+1]--; } void dfs(int nod) { submin[nod]=mint[nod]; submax[nod]=maxt[nod]; for(auto adj:con[nod]) { dfs(adj); submin[nod] = min(submin[nod], submin[adj]); submax[nod] = max(submax[nod], submax[adj]); } //cout<<nod<<" "<<mint[nod]<<" "<<submax[nod]<<" zzz\n"; if(nod>0) same_day(mint[nod],submax[nod]); } int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) { for(int i=0;i<N;i++) { con[i].clear(); mint[i]=INF; maxt[i]=-1; mars[i]=0; } for(int i=1;i<N;i++) { con[F[i]].push_back(i); } for(int i=0;i<M;i++) { for(int j=0;j<N-1;j++) { mint[S[i][j]] = min(mint[S[i][j]], j); maxt[S[i][j]] = max(maxt[S[i][j]], j); } } dfs(0); int cnt=1; for(int i=1;i<N-1;i++) { mars[i] += mars[i-1]; if(mars[i]==0) { cnt++; } } return cnt; }
#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...