QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111808#6406. Stage ClearAK_DreamWA 88ms527904kbC++141.8kb2023-06-08 20:59:392023-06-08 20:59:40

Judging History

This is the latest submission verdict.

  • [2024-08-15 21:05:17]
  • hack成功,自动添加数据
  • (/hack/778)
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-08 20:59:40]
  • Judged
  • Verdict: WA
  • Time: 88ms
  • Memory: 527904kb
  • [2023-06-08 20:59:39]
  • Submitted

answer

#include <bits/stdc++.h>
#define N 105
using namespace std;
typedef long long ll;

int n, m; ll ans;
struct dat {
	ll a, b;
	bool operator < (const dat _) const { 
		if ((a+b>0)!=(_.a+_.b>0)) return a+b>0;
		if (a+b>0) return a<_.a;
		else return b>_.b;
	}
	dat operator + (const dat _) const {
		dat r;
		r.a = max(a, a-b+_.a); 
		r.b = b-a+_.b-_.a+r.a;
		return r;
	}
} v[N], v2[N];

int e[N];
ll dp[(1<<26)+5], sum[N];
void solve1() {
	for (int i = 1, u, vv; i <= m; i++) {
		scanf("%d %d", &u, &vv);
		e[vv] |= 1<<(u-1); 
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[1] = 0;
	for (int s = 1; s < (1<<n); s++) {
		int c = __builtin_popcount(s), x = __lg(s&-s)+1;
		sum[c] = sum[c-1]-v[x].a+v[x].b;
		ll nw = dp[s]+sum[c];
		for (int i = 1; i <= n; i++) if ((~s>>(i-1)&1) && (e[i]&s)) {
			dp[s|(1<<(i-1))] = min(dp[s|(1<<(i-1))], max(dp[s],v[i].a-nw));
		}
	}
	ans = dp[(1<<n)-1];
}

vector<int> E[N]; 
int fa[N], vis[N];
void DP() {
	set<pair<dat,int> > st;
	dat nw = (dat){0,0}; vis[1] = 1;
	for (int i = 2; i <= n; i++) {
		vis[i] = 0; st.insert({v2[i]=v[i],i});
	}	
	while (!st.empty()) {
		int x = st.begin()->second; st.erase(st.begin());
		if (vis[fa[x]]) {
			nw = nw+v2[x]; continue;
		}
		st.erase({v2[fa[x]],fa[x]});
		v2[fa[x]] = v2[fa[x]]+v2[x];
		st.insert({v2[fa[x]],fa[x]});
	}
	ans = min(ans, nw.a);
}
void dfs(int x) {
	if (x > n) { DP(); return; }
	for (auto f : E[x]) {
		fa[x] = f; dfs(x+1);
	}
}
void solve2() {
	for (int i = 1, u, vv; i <= m; i++) {
		scanf("%d %d", &u, &vv);
		E[vv].push_back(u);
	}
	dfs(2);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 2; i <= n; i++) {
		scanf("%lld %lld", &v[i].a, &v[i].b);
	}
	ans = 1e18;
	if (n <= 26) solve1();
	else solve2();
	printf("%lld\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 88ms
memory: 527904kb

input:

4 4
4 2
5 3
2 6
1 2
1 3
2 4
3 4

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: -100
Wrong Answer
time: 67ms
memory: 527860kb

input:

15 14
254040392438309 117083115436273
500005748229691 557255157630172
821034233718230 865199673774998
659892147898798 987564141425694
81172575487567 811635577877255
751768357864605 341103322647288
454926350150218 140191090713900
921608121471585 659295670987251
223751724062143 505619245326640
8907765...

output:

966304985368047

result:

wrong answer 1st numbers differ - expected: '1665396301509143', found: '966304985368047'