답안 #417613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417613	2021-06-04T03:58:19 Z	huangqr	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	371 ms	119200 KB

worst_reporter2

#ifdef local
#define debug(x) cout<<#x<<" "<<x<<endl;
#else
#define debug(x)
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
const ll mod=1e9+7,lim=2e5+5,bitlim=15,inf=1e9;
vector<ll>adjl[lim];
vector<pl>costs[lim];
ll pwr[lim],cost[lim];
map<ll,ll> *mps[lim];
ll root[lim],nxt[lim];
ll vis[lim];

void dp(ll pos){
	if(adjl[pos].size() == 0){
		mps[pos] = new map<ll,ll>();
		mps[pos]->operator[](0)=0;
		mps[pos]->operator[](pwr[pos] + 1) = cost[pos];
	}
	else{
		ll maxsz=0,maxszidx=0;
		for(int i=0;i<adjl[pos].size();i++){
			ll u=adjl[pos][i];
			dp(u);
			if(mps[u]->size()>maxsz){
				maxsz=mps[u]->size();
				maxszidx=u;
			}
		}
		mps[pos] = mps[maxszidx];
		for(int i=0;i<adjl[pos].size();i++){
			ll u=adjl[pos][i];
			if(u==maxszidx)continue;
			for(auto p:*mps[u]){
				ll k,v;
				tie(k,v)=p;
				mps[pos]->operator[](k)+=v;
			}
		}
		if(root[pos]==pos){
			for(pl pr:costs[pos]){
				ll p,c;
				tie(p,c)=pr;
				mps[pos]->operator[](0) += c;
				mps[pos]->operator[](p + 1) += c;
			}
			for(pl pr:costs[pos]){
				ll p,c;
				tie(p,c)=pr;
				auto it=mps[pos]->upper_bound(p);
				ll rem=c;
				while(rem>0){
					it--;
					if(rem<=it->second)it->second-=rem,rem=0;
					else rem-=it->second,it=mps[pos]->erase(it);
				}
			}
		}
		else{
			mps[pos]->operator[](0) += cost[pos];
			mps[pos]->operator[](pwr[pos] + 1) += cost[pos];
			auto it=mps[pos]->upper_bound(pwr[pos]);
			ll rem=cost[pos];
			while(rem>0){
				it--;
				if(rem<=it->second)it->second-=rem,rem=0;
				else rem-=it->second,it=mps[pos]->erase(it);
			}
		}
	}
	return;
}

ll dfs(ll pos,ll idx){
	vis[pos]=idx;
	if(vis[nxt[pos]]==0){
		ll k = dfs(nxt[pos],idx);
		if(k!=-1){
			root[pos]=k;
			costs[k].emplace_back(pwr[pos],cost[pos]);
			if(k!=pos)return k;
		}
		return -1;
	}
	else if(vis[nxt[pos]]==idx){
		root[nxt[pos]]=root[pos]=nxt[pos];
		costs[nxt[pos]].emplace_back(pwr[pos],cost[pos]);
		if(nxt[pos]==pos)return -1;
		else return nxt[pos];
	}
	else return -1;
}



int main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL);
	ll n;
	cin>>n;
	fill(root,root+n+1,-1);
	for(int i=1;i<=n;i++){
		ll a;
		cin>>a>>pwr[i]>>cost[i];
		nxt[i]=a;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0)dfs(i,i);
	}
	for(int i=1;i<=n;i++){
		if(i!=nxt[i]&&root[i]==-1){
			if(root[nxt[i]]!=-1){
				adjl[root[nxt[i]]].push_back(i);
			}
			else adjl[nxt[i]].push_back(i);
		}
	}
	ll ans=0;
/*	for(int i=1;i<=n;i++){
		cout<<i<<": "<<root[i]<<"\n";
	}*/
	for(int i=1;i<=n;i++){
		if(root[i]==i){
	//		cout<<"rooti=i:"<<i<<"\n";
			dp(i);
			ans+=mps[i]->begin()->second;
		}
	}
	cout<<ans<<"\n";
/*	for(int i=1;i<=n;i++){
		cout<<i<<": ";
		for(auto x:adjl[i])cout<<x<<" ";
		cout<<"\n";
	}*/
	//dp(1);
	//cout<<mps[1]->begin()->second<<"\n";
	return 0;
}

Compilation message

worst_reporter2.cpp: In function 'void dp(ll)':
worst_reporter2.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i=0;i<adjl[pos].size();i++){
      |               ~^~~~~~~~~~~~~~~~~
worst_reporter2.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   29 |    if(mps[u]->size()>maxsz){
      |       ~~~~~~~~~~~~~~^~~~~~
worst_reporter2.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0;i<adjl[pos].size();i++){
      |               ~^~~~~~~~~~~~~~~~~

Subtask #1

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9676 KB	Output is correct
2	Correct	7 ms	9712 KB	Output is correct
3	Correct	6 ms	9712 KB	Output is correct
4	Correct	6 ms	9676 KB	Output is correct
5	Correct	13 ms	11424 KB	Output is correct
6	Correct	11 ms	11024 KB	Output is correct
7	Correct	10 ms	10756 KB	Output is correct
8	Correct	11 ms	11460 KB	Output is correct
9	Correct	11 ms	10912 KB	Output is correct
10	Correct	10 ms	10828 KB	Output is correct
11	Correct	9 ms	10568 KB	Output is correct
12	Correct	12 ms	10956 KB	Output is correct
13	Correct	10 ms	11008 KB	Output is correct
14	Correct	9 ms	10632 KB	Output is correct
15	Correct	10 ms	10644 KB	Output is correct
16	Correct	12 ms	11856 KB	Output is correct
17	Correct	11 ms	11212 KB	Output is correct
18	Correct	9 ms	10592 KB	Output is correct
19	Correct	10 ms	11212 KB	Output is correct
20	Correct	10 ms	10956 KB	Output is correct
21	Correct	9 ms	10956 KB	Output is correct
22	Correct	11 ms	11312 KB	Output is correct
23	Correct	9 ms	11084 KB	Output is correct
24	Correct	10 ms	11160 KB	Output is correct
25	Correct	10 ms	10976 KB	Output is correct
26	Correct	13 ms	11264 KB	Output is correct
27	Correct	11 ms	11264 KB	Output is correct
28	Correct	10 ms	11212 KB	Output is correct
29	Correct	10 ms	11260 KB	Output is correct
30	Correct	10 ms	11012 KB	Output is correct
31	Correct	10 ms	11008 KB	Output is correct

Subtask #2

65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9676 KB	Output is correct
2	Correct	7 ms	9712 KB	Output is correct
3	Correct	6 ms	9712 KB	Output is correct
4	Correct	6 ms	9676 KB	Output is correct
5	Correct	13 ms	11424 KB	Output is correct
6	Correct	11 ms	11024 KB	Output is correct
7	Correct	10 ms	10756 KB	Output is correct
8	Correct	11 ms	11460 KB	Output is correct
9	Correct	11 ms	10912 KB	Output is correct
10	Correct	10 ms	10828 KB	Output is correct
11	Correct	9 ms	10568 KB	Output is correct
12	Correct	12 ms	10956 KB	Output is correct
13	Correct	10 ms	11008 KB	Output is correct
14	Correct	9 ms	10632 KB	Output is correct
15	Correct	10 ms	10644 KB	Output is correct
16	Correct	12 ms	11856 KB	Output is correct
17	Correct	11 ms	11212 KB	Output is correct
18	Correct	9 ms	10592 KB	Output is correct
19	Correct	10 ms	11212 KB	Output is correct
20	Correct	10 ms	10956 KB	Output is correct
21	Correct	9 ms	10956 KB	Output is correct
22	Correct	11 ms	11312 KB	Output is correct
23	Correct	9 ms	11084 KB	Output is correct
24	Correct	10 ms	11160 KB	Output is correct
25	Correct	10 ms	10976 KB	Output is correct
26	Correct	13 ms	11264 KB	Output is correct
27	Correct	11 ms	11264 KB	Output is correct
28	Correct	10 ms	11212 KB	Output is correct
29	Correct	10 ms	11260 KB	Output is correct
30	Correct	10 ms	11012 KB	Output is correct
31	Correct	10 ms	11008 KB	Output is correct
32	Correct	11 ms	11444 KB	Output is correct
33	Correct	351 ms	93964 KB	Output is correct
34	Correct	285 ms	69296 KB	Output is correct
35	Correct	371 ms	90868 KB	Output is correct
36	Correct	285 ms	69308 KB	Output is correct
37	Correct	220 ms	50868 KB	Output is correct
38	Correct	210 ms	46404 KB	Output is correct
39	Correct	183 ms	61764 KB	Output is correct
40	Correct	156 ms	61764 KB	Output is correct
41	Correct	120 ms	61748 KB	Output is correct
42	Correct	163 ms	46240 KB	Output is correct
43	Correct	168 ms	46276 KB	Output is correct
44	Correct	315 ms	119200 KB	Output is correct
45	Correct	227 ms	83576 KB	Output is correct
46	Correct	117 ms	46084 KB	Output is correct
47	Correct	255 ms	68576 KB	Output is correct
48	Correct	151 ms	61688 KB	Output is correct
49	Correct	139 ms	61636 KB	Output is correct
50	Correct	229 ms	74944 KB	Output is correct
51	Correct	135 ms	62520 KB	Output is correct
52	Correct	244 ms	69632 KB	Output is correct
53	Correct	143 ms	62516 KB	Output is correct
54	Correct	217 ms	74472 KB	Output is correct
55	Correct	230 ms	70940 KB	Output is correct
56	Correct	215 ms	70756 KB	Output is correct
57	Correct	200 ms	71624 KB	Output is correct
58	Correct	217 ms	64120 KB	Output is correct
59	Correct	212 ms	64192 KB	Output is correct

Subtask #3

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9676 KB	Output is correct
2	Correct	7 ms	9712 KB	Output is correct
3	Correct	6 ms	9712 KB	Output is correct
4	Correct	6 ms	9676 KB	Output is correct
5	Correct	13 ms	11424 KB	Output is correct
6	Correct	11 ms	11024 KB	Output is correct
7	Correct	10 ms	10756 KB	Output is correct
8	Correct	11 ms	11460 KB	Output is correct
9	Correct	11 ms	10912 KB	Output is correct
10	Correct	10 ms	10828 KB	Output is correct
11	Correct	9 ms	10568 KB	Output is correct
12	Correct	12 ms	10956 KB	Output is correct
13	Correct	10 ms	11008 KB	Output is correct
14	Correct	9 ms	10632 KB	Output is correct
15	Correct	10 ms	10644 KB	Output is correct
16	Correct	12 ms	11856 KB	Output is correct
17	Correct	11 ms	11212 KB	Output is correct
18	Correct	9 ms	10592 KB	Output is correct
19	Correct	10 ms	11212 KB	Output is correct
20	Correct	10 ms	10956 KB	Output is correct
21	Correct	9 ms	10956 KB	Output is correct
22	Correct	11 ms	11312 KB	Output is correct
23	Correct	9 ms	11084 KB	Output is correct
24	Correct	10 ms	11160 KB	Output is correct
25	Correct	10 ms	10976 KB	Output is correct
26	Correct	13 ms	11264 KB	Output is correct
27	Correct	11 ms	11264 KB	Output is correct
28	Correct	10 ms	11212 KB	Output is correct
29	Correct	10 ms	11260 KB	Output is correct
30	Correct	10 ms	11012 KB	Output is correct
31	Correct	10 ms	11008 KB	Output is correct
32	Correct	11 ms	11444 KB	Output is correct
33	Correct	351 ms	93964 KB	Output is correct
34	Correct	285 ms	69296 KB	Output is correct
35	Correct	371 ms	90868 KB	Output is correct
36	Correct	285 ms	69308 KB	Output is correct
37	Correct	220 ms	50868 KB	Output is correct
38	Correct	210 ms	46404 KB	Output is correct
39	Correct	183 ms	61764 KB	Output is correct
40	Correct	156 ms	61764 KB	Output is correct
41	Correct	120 ms	61748 KB	Output is correct
42	Correct	163 ms	46240 KB	Output is correct
43	Correct	168 ms	46276 KB	Output is correct
44	Correct	315 ms	119200 KB	Output is correct
45	Correct	227 ms	83576 KB	Output is correct
46	Correct	117 ms	46084 KB	Output is correct
47	Correct	255 ms	68576 KB	Output is correct
48	Correct	151 ms	61688 KB	Output is correct
49	Correct	139 ms	61636 KB	Output is correct
50	Correct	229 ms	74944 KB	Output is correct
51	Correct	135 ms	62520 KB	Output is correct
52	Correct	244 ms	69632 KB	Output is correct
53	Correct	143 ms	62516 KB	Output is correct
54	Correct	217 ms	74472 KB	Output is correct
55	Correct	230 ms	70940 KB	Output is correct
56	Correct	215 ms	70756 KB	Output is correct
57	Correct	200 ms	71624 KB	Output is correct
58	Correct	217 ms	64120 KB	Output is correct
59	Correct	212 ms	64192 KB	Output is correct
60	Incorrect	6 ms	9716 KB	Output isn't correct
61	Halted	0 ms	0 KB	-