QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527630#6659. 외곽 순환 도로 2NianFeng0 25ms19008kbC++141.4kb2024-08-22 17:49:282024-08-26 15:53:15

Judging History

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

  • [2024-08-26 15:53:15]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:25ms
  • 内存:19008kb
  • [2024-08-26 15:49:13]
  • 管理员手动重测该提交记录
  • 测评结果:0
  • 用时:22ms
  • 内存:18952kb
  • [2024-08-22 17:49:29]
  • 评测
  • [2024-08-22 17:49:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
vector<int>G[N];
vector<long long>c,w;
int v,h[N];
long long f[N][2][2][2],g[2][2][2],o;
void dfs(int x){
    if(G[x].empty()){
        f[x][0][0][0]=f[x][1][1][1]=0;
        return h[x]=++v,void();
    }
    for(int y : G[x]){
        dfs(y);
        if(!h[x])
            for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)
                f[x][i][j][k]=max(f[y][i^1][j][k]+c[y-1],f[y][i][j][k]);
        else{
            for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)
                g[i][j][k]=-1e18;
            for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)
            for(int a=0;a<=1;a++) for(int b=0;b<=1;b++) for(int z=0;z<=1;z++)
                g[i][j][k]=max(g[i][j][k],f[x][i][j][a]+f[y][z][b][k]+c[y-1]*(i^z)+w[h[x]-1]*(a^b));
            for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)
                f[x][i][j][k]=g[i][j][k];
        } h[x]=h[y];
    }
}
long long place_police(vector<int> P, vector<long long> C, vector<long long> W){
    for(int i=0;i<P.size();i++)
        G[P[i]].push_back(i+1);
    memset(f,0xcf,sizeof(f));
    c=C,w=W,dfs(0),o=-1e18;
    for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)
        o=max(o,f[0][i][j][k]+W.back()*(j^k)); o=-o;
    for(int x : C) o+=x; for(int x : W) o+=x;
    return o;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 12792kb

input:

5
0 452912
0 820899
0 79369
0 232463
1000000000000 1000000000000 1000000000000 1000000000000

output:

-4002908987591

result:

wrong answer 1st lines differ - expected: '532281', found: '-4002908987591'

Subtask #2:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 25ms
memory: 19008kb

input:

99997
0 122727
0 267270
0 846212
0 454122
0 805668
0 614161
0 7805
0 173284
0 684707
0 269129
0 930945
0 1101
0 992427
0 297412
0 759787
0 227130
0 120418
0 90914
0 333684
0 46144
0 519912
0 171490
0 823586
0 121787
0 674177
0 560254
0 753090
0 853359
0 465464
0 655527
0 631303
0 919012
0 597126
0 1...

output:

-100068710106949947

result:

wrong answer 1st lines differ - expected: '24980330181', found: '-100068710106949947'

Subtask #3:

score: 0
Wrong Answer

Test #36:

score: 0
Wrong Answer
time: 3ms
memory: 13044kb

input:

11
0 9
0 8
2 0
3 7
3 1
2 6
0 0
7 7
7 1
9 6
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000

output:

-6004364279807

result:

wrong answer 1st lines differ - expected: '1', found: '-6004364279807'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #77:

score: 0
Wrong Answer
time: 4ms
memory: 15708kb

input:

50311
0 962897543825
1 887020369743
2 363658802934
3 481009844166
4 1099712574
5 858320882162
6 521927434762
7 379344260539
8 73024776148
9 634183458545
10 869560347910
11 81581323331
12 750044298516
13 307013017409
14 306226274039
15 423923546601
16 482114694167
17 849292461119
18 299993045938
19 7...

output:

-25304939170371051

result:

wrong answer 1st lines differ - expected: '939418184213', found: '-25304939170371051'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%