QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#884087#6298. ColoringAMATSUKAZECompile Error//C++144.9kb2025-02-05 21:16:172025-02-05 21:16:19

Judging History

This is the latest submission verdict.

  • [2025-02-05 21:16:19]
  • Judged
  • [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;



}

Details

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