QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#484919#6298. ColoringBalintRWA 7ms198908kbC++203.0kb2024-07-20 07:01:572024-07-20 07:01:57

Judging History

你现在查看的是最新测评结果

  • [2024-07-20 07:01:57]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:198908kb
  • [2024-07-20 07:01:57]
  • 提交

answer

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

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

const int MN = 5005;
int n, src;
int arr[MN], wrr[MN], prr[MN];
vi adjList[MN];
ll dp[MN][MN];
vi loop;
int lsz, mxt;

void dfs(int n1){
    for(int n2 : adjList[n1]){
        dfs(n2);
        ll v = 0;
        FR(i, mxt) dp[n1][i] += v = max(v, dp[n2][i]);
    }
    FR(i, mxt) dp[n1][i] += (i & 1)*wrr[n1] - (ll) i*prr[n1];
}

bool vis[MN];

void genLoop(){
    int n1 = src;
    while(!vis[n1]){
        vis[n1] = true;
        loop.pb(n1);
        n1 = arr[n1];
    }
    if(n1 != src) loop = {src};
    reverse(loop.begin()+1, loop.end());
    lsz = SZ(loop);
    mxt = (n-lsz)+4;
}

ll cycArr[MN*MN/4], difArr[MN*MN/4];

ll solve(){
    int lvls = mxt/2;
    int sz = lvls*lsz;
    FR(k, lvls) FR(i, lsz){
        cycArr[k*lsz+i] = dp[loop[i]][k*2];
        difArr[k*lsz+i] = dp[loop[i]][k*2+1] - dp[loop[i]][k*2];
    }

    ll ans = 0;
    FORR(i, sz-1, 0) cycArr[i] += cycArr[i+1];

    FR(i, sz-lsz+1){
        ll v = cycArr[i] - cycArr[i+lsz];
        ll mx = 0, cur = 0;
        FR(j, lsz) mx = max(mx, cur += difArr[i+j]);
        ans = max(ans, v + mx);
    }

    return ans;
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n >> src;
    src--;
    FR(i, n) cin >> wrr[i];
    FR(i, n) cin >> prr[i];
    FR(i, n) cin >> arr[i], arr[i]--;

    genLoop();
    FR(i, n) if(!vis[i]) adjList[arr[i]].pb(i);
    for(int n1 : loop) dfs(n1);
    dp[src][0] = -LLINF;
    FOR(i, 1, mxt) dp[src][i] += prr[src];

    //dbgArr(loop, lsz);
    //FR(i, n) dbgArr(dp[i], mxt);


    if(lsz == 1) return !printf("%lld\n", dp[src][1]);
    if(lsz == 2){
        int n2 = loop[1];
        ll v = max({dp[src][1], dp[src][1] + dp[n2][1], dp[src][2]});
        return !printf("%lld\n", v);
    }

    cout << solve() << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5724kb

input:

3 1
-1 -1 2
1 0 0
3 1 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5716kb

input:

10 8
36175808 53666444 14885614 -14507677 -92588511 52375931 -87106420 -7180697 -158326918 98234152
17550389 45695943 55459378 18577244 93218347 64719200 84319188 34410268 20911746 49221094
8 1 2 2 8 8 4 7 8 4

output:

35343360

result:

ok 1 number(s): "35343360"

Test #3:

score: -100
Wrong Answer
time: 7ms
memory: 198908kb

input:

5000 1451
531302480 400140870 -664321146 -376787089 -440627168 -672055995 924309614 2764785 -225700856 880835131 -435550509 162278080 -635253658 251803267 -499868931 213283508 603121701 -603347266 541062018 -502078443 -585620031 486788884 864390909 -670529282 -63580194 512939729 691685896 481123612 ...

output:

80519799290

result:

wrong answer 1st numbers differ - expected: '83045140866', found: '80519799290'