Submission #103347

---

Source Code Expand

 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, pair<int, int> > state;
 
/*
*/
 
#define INV -10000000
 
pair<int, pair<int, int> > memo[100][102][102];
int val[100];
vector<int> child[100];
 
int N;
 
state solve(int P, int alpha, int beta, bool sgn)
{
if(memo[P][alpha][beta].first != INV) return memo[P][alpha][beta];
if(child[P].size() == 0){
return memo[P][alpha][beta] = make_pair((sgn ? 1 : -1) * val[P], make_pair(1, 1));
}
vector<int> perm;
for(int i=0;i<child[P].size();i++) perm.push_back(i);
int rMin=100000000, rMax=-1;
int alpha_ = alpha, beta_ = beta;
int ret = -1;
//printf("%d %d %d\n", P, alpha, beta);
do{
//test
alpha = alpha_; beta = beta_;
int sMin = 0, sMax = 0;
if(sgn){
for(int _i=0;_i<child[P].size();_i++){ int i = perm[_i];
state tmp = solve(child[P][i], alpha, beta, !sgn);
alpha = max(alpha, tmp.first);
sMin += tmp.second.first;
sMax += tmp.second.second;
if(beta <= alpha) break;
}
rMin = min(rMin, sMin);
rMax = max(rMax, sMax);
ret = alpha;
}else{
for(int _i=0;_i<child[P].size();_i++){ int i = perm[_i];
state tmp = solve(child[P][i], alpha, beta, !sgn);
beta = min(beta, tmp.first);
sMin += tmp.second.first;
sMax += tmp.second.second;
if(beta <= alpha) break;
}
rMin = min(rMin, sMin);
rMax = max(rMax, sMax);
ret = beta;
}
}while(next_permutation(perm.begin(), perm.end()));
return memo[P][alpha_][beta_] = make_pair(ret, make_pair(rMin, rMax));
}
 
int main()
{
scanf("%d", &N);
for(int i=0;i<N;i++) scanf("%d", val+i);
for(int i=0;i<N;i++){
int k, t;
scanf("%d", &k);
for(;k--;){
scanf("%d", &t);
--t;
child[i].push_back(t);
}
}
vector<int> st;
for(int i=0;i<N;i++) st.push_back(val[i]);
st.push_back(-10000000);
st.push_back(10000000);
sort(st.begin(), st.end());
st.erase(unique(st.begin(), st.end()), st.end());
for(int i=0;i<N;i++) val[i] = lower_bound(st.begin(), st.end(), val[i]) - st.begin();
int K = st.size();
for(int i=0;i<N;i++)
for(int j=0;j<K;j++)
for(int k=0;k<K;k++) memo[i][j][k] = make_pair(INV, make_pair(0, 0));
pair<int, int> ret = solve(0, 0, K-1, true).second;
printf("%d %d\n", ret.first, ret.second);
return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:64: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:65: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:68: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:70: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result