답안 #418931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418931	2021-06-06T08:52:40 Z	ryansee	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	384 ms	109040 KB

worst_reporter2

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusive
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (200006)
ll n, mx, P[MAXN], A[MAXN], C[MAXN], ans;
bitset<MAXN> vis, in;
vector<int> stk, cy;
vector<int> v[MAXN];
void cycle(int x) {
	vis[x]=1;
	stk.eb(x);
	if(!vis[P[x]]) cycle(P[x]);
	else {
		while(1) {
			if(stk.empty()) {
				cy.clear();
				break;
			}
			ll y=stk.back(); stk.pop_back();
			cy.eb(y);
			if(y==P[x]) break;
		}
	}
}
map<ll,ll> *mp[MAXN];
void dfs(int x) {
	mp[x] = new map<ll,ll>;
	for(auto i:v[x]) {
		dfs(i);
		if(mp[x]->size() < mp[i]->size()) mp[x] = mp[i];
	}
	for(auto i:v[x]) if(mp[x] != mp[i]) {
		for(auto j:*mp[i]) (*mp[x])[j.f] += j.s;
	}
	(*mp[x])[mx] += C[x];
	(*mp[x])[A[x]] -= C[x];
	(*mp[x])[A[x]-1] += C[x];
	auto it = mp[x]->find(A[x]);
	while(it->s < 0) {
		auto tmp = next(it);
		assert(tmp != mp[x]->end());
		tmp->s += it->s;
		mp[x]->erase(it);
		it = tmp;
	}
	if(it->s == 0) mp[x]->erase(it);
}
int main() {
	FAST
	cin>>n;
	FOR(i,1,n) cin>>P[i]>>A[i]>>C[i];
	mx = *max_element(A+1, A+n+1) + 1;
	FOR(i,1,n) A[i] = mx - A[i];
	FOR(i,1,n) if(P[i]^i) in[P[i]]=1;
	FOR(i,1,n) if(!in[i]) {
		stk.clear(), cy.clear();
		cycle(i);
		if(cy.size() <= 1) continue;
		sort(all(cy), [](int x,int y){return A[x]>A[y];});
		FOR(i,0,siz(cy)-2) {
			P[cy[i]] = cy[i+1];
		}
		P[cy.back()]=cy.back();
	}
	FOR(i,1,n) if(!vis[i]) {
		stk.clear(), cy.clear();
		cycle(i);
		if(cy.size() <= 1) continue;
		sort(all(cy), [](int x,int y){return A[x]>A[y];});
		FOR(i,0,siz(cy)-2) {
			P[cy[i]] = cy[i+1];
		}
		P[cy.back()]=cy.back();
	}
	FOR(i,1,n) if(P[i] ^ i) v[P[i]].eb(i);
	FOR(i,1,n) if(P[i] == i) {
		dfs(i);
		ans += (*mp[i])[mx];
	}
	cout<<ans<<'\n';
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	9 ms	6480 KB	Output is correct
6	Correct	8 ms	6168 KB	Output is correct
7	Correct	8 ms	5964 KB	Output is correct
8	Correct	12 ms	6628 KB	Output is correct
9	Correct	8 ms	6092 KB	Output is correct
10	Correct	7 ms	5964 KB	Output is correct
11	Correct	8 ms	5748 KB	Output is correct
12	Correct	8 ms	6348 KB	Output is correct
13	Correct	7 ms	6348 KB	Output is correct
14	Correct	8 ms	5964 KB	Output is correct
15	Correct	7 ms	6024 KB	Output is correct
16	Correct	10 ms	6988 KB	Output is correct
17	Correct	8 ms	6288 KB	Output is correct
18	Correct	7 ms	5672 KB	Output is correct
19	Correct	8 ms	6220 KB	Output is correct
20	Correct	7 ms	6092 KB	Output is correct
21	Correct	7 ms	6092 KB	Output is correct
22	Correct	7 ms	6104 KB	Output is correct
23	Correct	8 ms	5832 KB	Output is correct
24	Correct	8 ms	6220 KB	Output is correct
25	Correct	7 ms	6068 KB	Output is correct
26	Correct	7 ms	6348 KB	Output is correct
27	Correct	9 ms	6220 KB	Output is correct
28	Correct	8 ms	6348 KB	Output is correct
29	Correct	8 ms	6476 KB	Output is correct
30	Correct	8 ms	6476 KB	Output is correct
31	Correct	8 ms	6436 KB	Output is correct

Subtask #2
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	9 ms	6480 KB	Output is correct
6	Correct	8 ms	6168 KB	Output is correct
7	Correct	8 ms	5964 KB	Output is correct
8	Correct	12 ms	6628 KB	Output is correct
9	Correct	8 ms	6092 KB	Output is correct
10	Correct	7 ms	5964 KB	Output is correct
11	Correct	8 ms	5748 KB	Output is correct
12	Correct	8 ms	6348 KB	Output is correct
13	Correct	7 ms	6348 KB	Output is correct
14	Correct	8 ms	5964 KB	Output is correct
15	Correct	7 ms	6024 KB	Output is correct
16	Correct	10 ms	6988 KB	Output is correct
17	Correct	8 ms	6288 KB	Output is correct
18	Correct	7 ms	5672 KB	Output is correct
19	Correct	8 ms	6220 KB	Output is correct
20	Correct	7 ms	6092 KB	Output is correct
21	Correct	7 ms	6092 KB	Output is correct
22	Correct	7 ms	6104 KB	Output is correct
23	Correct	8 ms	5832 KB	Output is correct
24	Correct	8 ms	6220 KB	Output is correct
25	Correct	7 ms	6068 KB	Output is correct
26	Correct	7 ms	6348 KB	Output is correct
27	Correct	9 ms	6220 KB	Output is correct
28	Correct	8 ms	6348 KB	Output is correct
29	Correct	8 ms	6476 KB	Output is correct
30	Correct	8 ms	6476 KB	Output is correct
31	Correct	8 ms	6436 KB	Output is correct
32	Correct	9 ms	6528 KB	Output is correct
33	Correct	357 ms	82764 KB	Output is correct
34	Correct	279 ms	58040 KB	Output is correct
35	Correct	352 ms	79724 KB	Output is correct
36	Correct	284 ms	58112 KB	Output is correct
37	Correct	212 ms	39292 KB	Output is correct
38	Correct	191 ms	33272 KB	Output is correct
39	Correct	235 ms	59248 KB	Output is correct
40	Correct	189 ms	59068 KB	Output is correct
41	Correct	138 ms	58948 KB	Output is correct
42	Correct	221 ms	45116 KB	Output is correct
43	Correct	227 ms	44992 KB	Output is correct
44	Correct	336 ms	109040 KB	Output is correct
45	Correct	273 ms	73400 KB	Output is correct
46	Correct	139 ms	33200 KB	Output is correct
47	Correct	340 ms	54232 KB	Output is correct
48	Correct	264 ms	47252 KB	Output is correct
49	Correct	135 ms	47276 KB	Output is correct
50	Correct	268 ms	49632 KB	Output is correct
51	Correct	138 ms	37136 KB	Output is correct
52	Correct	251 ms	55256 KB	Output is correct
53	Correct	160 ms	48260 KB	Output is correct
54	Correct	150 ms	58956 KB	Output is correct
55	Correct	249 ms	56984 KB	Output is correct
56	Correct	238 ms	63084 KB	Output is correct
57	Correct	246 ms	66168 KB	Output is correct
58	Correct	239 ms	63664 KB	Output is correct
59	Correct	262 ms	63672 KB	Output is correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	9 ms	6480 KB	Output is correct
6	Correct	8 ms	6168 KB	Output is correct
7	Correct	8 ms	5964 KB	Output is correct
8	Correct	12 ms	6628 KB	Output is correct
9	Correct	8 ms	6092 KB	Output is correct
10	Correct	7 ms	5964 KB	Output is correct
11	Correct	8 ms	5748 KB	Output is correct
12	Correct	8 ms	6348 KB	Output is correct
13	Correct	7 ms	6348 KB	Output is correct
14	Correct	8 ms	5964 KB	Output is correct
15	Correct	7 ms	6024 KB	Output is correct
16	Correct	10 ms	6988 KB	Output is correct
17	Correct	8 ms	6288 KB	Output is correct
18	Correct	7 ms	5672 KB	Output is correct
19	Correct	8 ms	6220 KB	Output is correct
20	Correct	7 ms	6092 KB	Output is correct
21	Correct	7 ms	6092 KB	Output is correct
22	Correct	7 ms	6104 KB	Output is correct
23	Correct	8 ms	5832 KB	Output is correct
24	Correct	8 ms	6220 KB	Output is correct
25	Correct	7 ms	6068 KB	Output is correct
26	Correct	7 ms	6348 KB	Output is correct
27	Correct	9 ms	6220 KB	Output is correct
28	Correct	8 ms	6348 KB	Output is correct
29	Correct	8 ms	6476 KB	Output is correct
30	Correct	8 ms	6476 KB	Output is correct
31	Correct	8 ms	6436 KB	Output is correct
32	Correct	9 ms	6528 KB	Output is correct
33	Correct	357 ms	82764 KB	Output is correct
34	Correct	279 ms	58040 KB	Output is correct
35	Correct	352 ms	79724 KB	Output is correct
36	Correct	284 ms	58112 KB	Output is correct
37	Correct	212 ms	39292 KB	Output is correct
38	Correct	191 ms	33272 KB	Output is correct
39	Correct	235 ms	59248 KB	Output is correct
40	Correct	189 ms	59068 KB	Output is correct
41	Correct	138 ms	58948 KB	Output is correct
42	Correct	221 ms	45116 KB	Output is correct
43	Correct	227 ms	44992 KB	Output is correct
44	Correct	336 ms	109040 KB	Output is correct
45	Correct	273 ms	73400 KB	Output is correct
46	Correct	139 ms	33200 KB	Output is correct
47	Correct	340 ms	54232 KB	Output is correct
48	Correct	264 ms	47252 KB	Output is correct
49	Correct	135 ms	47276 KB	Output is correct
50	Correct	268 ms	49632 KB	Output is correct
51	Correct	138 ms	37136 KB	Output is correct
52	Correct	251 ms	55256 KB	Output is correct
53	Correct	160 ms	48260 KB	Output is correct
54	Correct	150 ms	58956 KB	Output is correct
55	Correct	249 ms	56984 KB	Output is correct
56	Correct	238 ms	63084 KB	Output is correct
57	Correct	246 ms	66168 KB	Output is correct
58	Correct	239 ms	63664 KB	Output is correct
59	Correct	262 ms	63672 KB	Output is correct
60	Correct	4 ms	5032 KB	Output is correct
61	Correct	3 ms	4940 KB	Output is correct
62	Correct	4 ms	4940 KB	Output is correct
63	Correct	3 ms	4940 KB	Output is correct
64	Incorrect	384 ms	67236 KB	Output isn't correct
65	Halted	0 ms	0 KB	-

답안 #418931

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 65.0 / 65.0

Subtask #3 0 / 21.0

Subtask #1
14.0 / 14.0

Subtask #2
65.0 / 65.0

Subtask #3
0 / 21.0