이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,p[100005],i,u,w,d,sum,c;
vector<ll> v[100005],de;
pair<ll,ll> fruit[100005];
vector<vector<ll>> a;
map<ll,ll> mp;
map<ll,ll> ::iterator it;
multiset<ll> s;
multiset<ll> ::iterator is;
bool ar;
void dfs(ll x){
ll d=fruit[x].first;
ll w=fruit[x].second;
d=mp[d];
a[x][d]=w;
for(int i:v[x]){
dfs(i);
for(int j=1;j<=k;j++){
a[x][j]+=a[i][j];
}
}
for(int i=2;i<=k;i++) a[x][i]=max(a[x][i-1],a[x][i]);
}
int main(){
cin >> n >> m >> k;
ar=true;
for(i=2;i<=n;i++){
cin >> p[i];
if(i-1!=p[i]) ar=false;
v[p[i]].push_back(i);
}
for(i=1;i<=m;i++){
cin >> u >> d >> w;
if(w!=1) ar=false;
mp[d]=1;
fruit[u]={d,w};
sum+=w;
c++;
de.push_back(d);
}
if(ar==true){
reverse(de.begin(),de.end());
for(i=0;i<de.size();i++){
is=s.upper_bound(de[i]);
if(is!=s.end()) s.erase(is);
s.insert(de[i]);
}
cout << s.size();
return 0;
}
k=0;
for(it=mp.begin();it!=mp.end();it++){
k++;
mp[it->first]=k;
}
if(k>1000){
cout << sum;
return 0;
}
a=vector<vector<ll>> (n+1,vector<ll> (k+1,0));
dfs(1);
cout << a[1][k];
}
컴파일 시 표준 에러 (stderr) 메시지
magictree.cpp: In function 'int main()':
magictree.cpp:45:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(i=0;i<de.size();i++){
| ~^~~~~~~~~~
# | 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... |