QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#527644#6659. 외곽 순환 도로 2NianFengCompile Error//C++141.4kb2024-08-22 17:59:012024-08-22 17:59:01

Judging History

你现在查看的是测评时间为 2024-08-22 17:59:01 的历史记录

  • [2024-08-26 15:53:19]
  • 管理员手动重测本题所有提交记录
  • 测评结果:100
  • 用时:33ms
  • 内存:35108kb
  • [2024-08-22 17:59:01]
  • 评测
  • [2024-08-22 17:59:01]
  • 提交

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],ans;
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),ans=-1e18;
    for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)
        ans=max(ans,f[0][i][j][k]+W.back()*(j^k)); ans=-ans;
    for(long long x : C) ans+=x; for(long long x : W) ans+=x;
    return ans;
}

详细

cc1plus: fatal error: implementer.cpp: No such file or directory
compilation terminated.