QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#884087 | #6298. Coloring | AMATSUKAZE | Compile Error | / | / | C++14 | 4.9kb | 2025-02-05 21:16:17 | 2025-02-05 21:16:19 |
Judging History
This is the latest submission verdict.
- [2025-02-05 21:16:19]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2025-02-05 21:16:17]
- Submitted
answer
#include<bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define all(v) begin(v),end(v)
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; }
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, st; cin >> n >> st;
st--;
vector<ll> w(n);
rep(i,0,n) cin >> w[i];
vector ikeru(n, vector<int>(0));
vector<ll> p(n);
rep(i,0,n) cin >> p[i];
vector<int> deg(n);
vector<int> a(n);
rep(i,0,n) {
cin >> a[i];
a[i]--;
ikeru[a[i]].push_back(i);
deg[a[i]]++;
}
vector<int> mada;
rep(i,0,n) {
if (deg[i] == 0) {
mada.push_back(i);
}
}
vector<bool> is_cycle(n, true);
while(!mada.empty()){
int i = mada.back();
mada.pop_back();
is_cycle[i] = false;
deg[a[i]]--;
if(deg[a[i]] == 0) {
mada.push_back(a[i]);
}
}
vector child_tree(n, vector<int>(0));
vector dp(n, vector<ll>(1)); // total profit of each subtree (i), alternating white and black (j) times.
auto dfs = [&](auto self, int i) -> void {
vector<ll> tmp(2);
tmp[0] = 0;
tmp[1] = w[i];
for (int j: ikeru[i]) {
self(self, j);
int sx = (int)tmp.size();
int sy = (int)dp[j].size();
vector<ll> ntmp(max(sx, sy + 1), -2e18);
rep(x,0,sx) {
rep(y,0,sy) {
if ((x+y)%2 == 0) {
chmax(ntmp[max(x, y)], tmp[x] + dp[j][y]);
}else{
chmax(ntmp[max(x, y + 1)], tmp[x] + dp[j][y]);
}
}
}
swap(ntmp, tmp);
}
rep(x,0,(int)tmp.size()) {
tmp[x] -= p[i] * x;
}
swap(dp[i], tmp);
};
rep(i,0,n) {
if (is_cycle[i]) {
for (int j: ikeru[i]) {
if (is_cycle[j]) continue;
dfs(dfs, j);
child_tree[i].push_back(j);
}
}
}
ll ans = -4e18;
if (!is_cycle[st]) {
chmax(ans, p[st]);
chmax(ans, dp[st][1] + p[st]);
if ((int)dp[st].size() >= 3) {
chmax(ans, dp[st][2] + p[st]);
}
cout << ans << '\n';
return 0;
}
rep(i,0,n) {
if (is_cycle[i]) {
for (int j: child_tree[i]) {
rep(k,0,(int)dp[j].size()-1) {
chmax(dp[j][k+1], dp[j][k]);
}
}
}
}
vector<int> cycle_list;
int now = st;
do {
cycle_list.push_back(now);
for (int j: ikeru[now]) {
if (is_cycle[j]) {
now = j;
break;
}
}
} while(now != st);
// cycle junkai
int m = (int)cycle_list.size();
auto get = [&](int i, int j) -> ll {
ll ret = 0;
for (int x: child_tree[i]) {
ret += dp[x][min(j,(int)dp[x].size()-1)];
}
return ret;
};
if (m == 2) {
int x = cycle_list[0];
int y = cycle_list[1];
chmax(ans, p[x]);
chmax(ans, get(x, 1));
chmax(ans, get(x, 1) + get(y, 1) + p[y]);
cout << ans << '\n';
return 0;
}
vector<ll> tmp(m+1);
int sz = 1<<13;
vector<ll> seg(2*sz, -3e18);
auto seg_set = [&](int i) -> void {
seg[i+sz] = tmp[i];
i += sz;
i >>= 1;
while(i > 0) {
seg[i] = max(seg[i*2], seg[i*2+1]);
i >>= 1;
}
};
ll geta = 0;
seg_set(0);
rep(i,0,m) {
if (i > 0) geta -= p[cycle_list[i]];
ll tar = get(cycle_list[i], 1) + w[cycle_list[i]];
geta += tar;
tmp[i+1] = tmp[i] + get(cycle_list[i], 2) - p[cycle_list[i]] - tar;
seg_set(i+1);
/*
rep(j,0,m+1) {
cout << tmp[j] + geta << ' ';
}
cout << endl;
*/
chmax(ans, seg[1] + geta);
}
vector alls(n+4, vector<ll>(m+1));
rep(i,0,n+4){
rep(j,0,m) {
alls[i][j+1] += alls[i][j];
alls[i][j+1] += get(cycle_list[j], 2*i) - p[cycle_list[j]] * (2*i) + (j==0?p[cycle_list[j]]:0);
}
}
rep(i,0,(n+1)*m) {
ll tar1 = get(cycle_list[i%m], 2*(i/m)+3) - get(cycle_list[i%m], 2*(i/m)+2) + w[cycle_list[i%m]];
geta += tar1;
geta -= p[cycle_list[i%m]];
tmp[i%(m+1)] = alls[(i/m)+2][i%m+1] - alls[(i/m)+2][0] + alls[(i/m)+1][m] - alls[(i/m)+1][i%m+1] - geta;
seg_set(i%(m+1));
/*
rep(j,0,m+1) {
cout << tmp[j]+geta << ' ';
}
cout << endl;
*/
chmax(ans, seg[1] + geta);
}
cout << ans << endl;
}
详细
answer.code:6:12: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 6 | bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; } | ^~~~ answer.code:6:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 6 | bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; } | ^~~~ answer.code:7:12: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 7 | bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; } | ^~~~ answer.code:7:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 7 | bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; } | ^~~~ answer.code: In function ‘int main()’: answer.code:17:12: error: missing template arguments before ‘ikeru’ 17 | vector ikeru(n, vector<int>(0)); | ^~~~~ answer.code:26:9: error: ‘ikeru’ was not declared in this scope 26 | ikeru[a[i]].push_back(i); | ^~~~~ answer.code:48:12: error: missing template arguments before ‘child_tree’ 48 | vector child_tree(n, vector<int>(0)); | ^~~~~~~~~~ answer.code:49:12: error: missing template arguments before ‘dp’ 49 | vector dp(n, vector<ll>(1)); // total profit of each subtree (i), alternating white and black (j) times. | ^~ answer.code: In lambda function: answer.code:54:21: error: ‘ikeru’ was not declared in this scope 54 | for (int j: ikeru[i]) { | ^~~~~ answer.code:57:27: error: ‘dp’ was not declared in this scope; did you mean ‘p’? 57 | int sy = (int)dp[j].size(); | ^~ | p answer.code:73:14: error: ‘dp’ was not declared in this scope; did you mean ‘p’? 73 | swap(dp[i], tmp); | ^~ | p answer.code: In function ‘int main()’: answer.code:78:25: error: ‘ikeru’ was not declared in this scope 78 | for (int j: ikeru[i]) { | ^~~~~ answer.code:81:17: error: ‘child_tree’ was not declared in this scope 81 | child_tree[i].push_back(j); | ^~~~~~~~~~ answer.code:89:20: error: ‘dp’ was not declared in this scope; did you mean ‘p’? 89 | chmax(ans, dp[st][1] + p[st]); | ^~ | p answer.code:99:25: error: ‘child_tree’ was not declared in this scope 99 | for (int j: child_tree[i]) { | ^~~~~~~~~~ answer.code:100:30: error: ‘dp’ was not declared in this scope; did you mean ‘p’? 100 | rep(k,0,(int)dp[j].size()-1) { | ^~ answer.code:2:53: note: in definition of macro ‘rep’ 2 | #define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++) | ^ answer.code:111:21: error: ‘ikeru’ was not declared in this scope 111 | for (int j: ikeru[now]) { | ^~~~~ answer.code: In lambda function: answer.code:124:21: error: ‘child_tree’ was not declared in this scope 124 | for (int x: child_tree[i]) { | ^~~~~~~~~~ answer.code:125:20: error: ‘dp’ was not declared in this scope; did you mean ‘p’? 125 | ret += dp[x][min(j,(int)dp[x].size()-1)]; | ^~ | p answer.code: In function ‘int main()’: answer.code:170:12: error: missing template arguments before ‘alls’ 170 | vector alls(n+4, vector<ll>(m+1)); | ^~~~ answer.code:173:13: error: ‘alls’ was not declared in this scope; did you mean ‘all’? 173 | alls[i][j+1] += alls[i][j]; | ^~~~ | all answer.code:182:24: error: ‘alls’ was not declared in this scope; did you mean ‘all’? 182 | tmp[i%(m+1)] = alls[(i/m)+2][i%m+1] - alls[(i/m)+2][0] + alls[(i/m)+1][m] - alls[(i/m)+1][i%m+1] - geta; | ^~~~ | all