oj.uz

Submission #60518

# Submission time Handle Problem Language Result Execution time Memory
60518 2018-07-24T09:35:12 Z WA_TLE Friend (IOI14_friend) C++14
100 / 100
 71 ms 10216 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
//#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1e9+7;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
//llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
#include"friend.h"
int findSample(int n,int confidence[],int host[],int protocol[]){
	vector<int>kan;kan.reserve(n+n);
	vector<int>ket;ket.reserve(n+n);
	vector<int>dco(n);
	int i;
	dco[0]=0;
	kan.pub(-1);ket.pub(-1);
	for(i=1;i<n;i++){
		int ue=host[i];
		int hou=protocol[i];
		if(hou==0){dco[i]=kan.size();kan.pub(dco[ue]);ket.pub(1);}
		else if(hou==1){
			int mto=dco[ue];
			dco[ue]=kan.size();kan.pub(mto);ket.pub(2);
			dco[i]=kan.size();kan.pub(mto);ket.pub(2);
		}else if(hou==2){
			int mto=dco[ue];
			dco[ue]=kan.size();kan.pub(mto);ket.pub(3);
			dco[i]=kan.size();kan.pub(mto);ket.pub(3);
		}
	}
	int m=kan.size();
	vector<llint>use(m);
	vector<llint>nou(m);
	for(i=0;i<n;i++){use[dco[i]]+=confidence[i];}
	for(i=m-1;i>=0;i--){
		maxeq(use[i],nou[i]);
		int ter=kan[i];
		if(ket[i]==1){
			use[ter]+=nou[i];
			nou[ter]+=use[i];
		}else if(ket[i]==2){
			use[ter]+=use[i];
			nou[ter]+=nou[i];
		}else if(ket[i]==3){
			use[ter]=max(use[ter]+nou[i],nou[ter]+use[i]);
			nou[ter]+=nou[i];
		}
	}
	//for(i=0;i<m;i++){cout<<use[i]<<" "<<nou[i]<<" "<<kan[i]<<" "<<ket[i]<<endl;}
	return use[0];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 424 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 680 KB Output is correct
8 Correct 3 ms 684 KB Output is correct
9 Correct 2 ms 688 KB Output is correct
10 Correct 3 ms 692 KB Output is correct
11 Correct 2 ms 696 KB Output is correct
12 Correct 3 ms 836 KB Output is correct
13 Correct 3 ms 836 KB Output is correct
14 Correct 2 ms 836 KB Output is correct
15 Correct 4 ms 836 KB Output is correct
16 Correct 3 ms 836 KB Output is correct
17 Correct 3 ms 836 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 836 KB Output is correct
2 Correct 1 ms 836 KB Output is correct
3 Correct 4 ms 836 KB Output is correct
4 Correct 3 ms 836 KB Output is correct
5 Correct 4 ms 876 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 4 ms 876 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 888 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 920 KB Output is correct
2 Correct 4 ms 920 KB Output is correct
3 Correct 4 ms 932 KB Output is correct
4 Correct 3 ms 936 KB Output is correct
5 Correct 3 ms 948 KB Output is correct
6 Correct 3 ms 960 KB Output is correct
7 Correct 3 ms 964 KB Output is correct
8 Correct 4 ms 968 KB Output is correct
9 Correct 3 ms 976 KB Output is correct
10 Correct 3 ms 980 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1012 KB Output is correct
2 Correct 3 ms 1012 KB Output is correct
3 Correct 2 ms 1016 KB Output is correct
4 Correct 3 ms 1020 KB Output is correct
5 Correct 4 ms 1024 KB Output is correct
6 Correct 4 ms 1032 KB Output is correct
7 Correct 3 ms 1048 KB Output is correct
8 Correct 4 ms 1052 KB Output is correct
9 Correct 3 ms 1064 KB Output is correct
10 Correct 4 ms 1068 KB Output is correct
11 Correct 3 ms 1072 KB Output is correct
12 Correct 4 ms 1080 KB Output is correct
13 Correct 3 ms 1092 KB Output is correct
14 Correct 3 ms 1180 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 3 ms 1260 KB Output is correct
8 Correct 3 ms 1260 KB Output is correct
9 Correct 2 ms 1260 KB Output is correct
10 Correct 4 ms 1260 KB Output is correct
11 Correct 3 ms 1260 KB Output is correct
12 Correct 3 ms 1260 KB Output is correct
13 Correct 4 ms 1260 KB Output is correct
14 Correct 3 ms 1260 KB Output is correct
15 Correct 3 ms 1260 KB Output is correct
16 Correct 3 ms 1260 KB Output is correct
17 Correct 3 ms 1260 KB Output is correct
18 Correct 3 ms 1312 KB Output is correct
19 Correct 2 ms 1312 KB Output is correct
20 Correct 3 ms 1312 KB Output is correct
21 Correct 4 ms 1312 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1312 KB Output is correct
2 Correct 4 ms 1312 KB Output is correct
3 Correct 4 ms 1312 KB Output is correct
4 Correct 4 ms 1312 KB Output is correct
5 Correct 2 ms 1312 KB Output is correct
6 Correct 3 ms 1312 KB Output is correct
7 Correct 3 ms 1312 KB Output is correct
8 Correct 3 ms 1312 KB Output is correct
9 Correct 3 ms 1312 KB Output is correct
10 Correct 3 ms 1312 KB Output is correct
11 Correct 3 ms 1312 KB Output is correct
12 Correct 71 ms 7944 KB Output is correct
13 Correct 25 ms 7944 KB Output is correct
14 Correct 45 ms 9012 KB Output is correct
15 Correct 50 ms 10216 KB Output is correct