QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #116274 | #6659. 외곽 순환 도로 2 | youngsystem# | Compile Error | / | / | C++20 | 3.3kb | 2023-06-28 12:55:45 | 2024-05-31 18:26:58 |
Judging History
你现在查看的是测评时间为 2024-05-31 18:26:58 的历史记录
- [2024-05-31 18:26:58]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-06-28 12:55:45]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
long long dp[100005][2][2][2];
int dep[100005];
vector<int>v[100005];
vector<long long>qz[100005];
int n;
int yz[100005],cnt;
int yd[100005];
long long yq[100005];
int tl[100005],tr[100005];
long long nex[2][2][2];
void dfs(int x,int f)
{
dep[x]=dep[f]+1;
if(v[x].empty())
{
yz[++cnt]=x;
tl[x]=tr[x]=cnt;
return;
}
tl[x]=cnt+1;
for(int i=0;i<v[x].size();i++)
{
dfs(v[x][i],x);
}
tr[x]=cnt;
}
void solve(int x,int f)
{
if(v[x].empty())
{
dp[x][1][1][1]=0;
return;
}
for(int i=0;i<v[x].size();i++)
{
//printf("???%d %d\n",x,v[x][i]);
solve(v[x][i],x);
/*for(int j=0;j<=1;j++)
{
for(int k=0;k<=1;k++)
{
for(int l=0;l<=1;l++)
{
printf("orz%d %d %d %lld\n",j,k,l,dp[v[x][i]][j][k][l]);
}
}
}*/
if(i==0)
{
for(int j=0;j<=1;j++)
{
for(int k=0;k<=1;k++)
{
for(int l=0;l<=1;l++)
{
dp[x][j][k][l]=dp[v[x][i]][j][k][l];
dp[x][0][0][l]=min(dp[x][0][0][l],dp[v[x][i]][j][k][l]+qz[x][i]);
}
}
}
continue;
}
for(int j=0;j<=1;j++)
{
for(int k=0;k<=1;k++)
{
for(int l=0;l<=1;l++)
{
nex[j][k][l]=1000000000000000000LL;
}
}
}
for(int j1=0;j1<=1;j1++)
{
for(int k1=0;k1<=1;k1++)
{
for(int l1=0;l1<=1;l1++)
{
for(int j2=0;j2<=1;j2++)
{
for(int k2=0;k2<=1;k2++)
{
for(int l2=0;l2<=1;l2++)
{
nex[j1][0][l1&l2]=min(nex[j1][0][l1&l2],dp[x][j1][k1][l1]+dp[v[x][i]][j2][k2][l2]+qz[x][i]);
nex[j1][0][0]=min(nex[j1][0][0],dp[x][j1][k1][l1]+dp[v[x][i]][j2][k2][l2]+qz[x][i]+yq[tl[v[x][i]]-1]);
if(k1==0||j2==0||(yd[tr[v[x][i-1]]]+yd[tl[v[x][i]]])%2==1)
{
nex[j1][k2][l1&l2]=min(nex[j1][k2][l1&l2],dp[x][j1][k1][l1]+dp[v[x][i]][j2][k2][l2]);
}
if(j2==0||k1==0)nex[j1][k2][0]=min(nex[j1][k2][0],dp[x][j1][k1][l1]+dp[v[x][i]][j2][k2][l2]+yq[tl[v[x][i]]-1]);
else nex[j1][k2][l1&l2]=min(nex[j1][k2][l1&l2],dp[x][j1][k1][l1]+dp[v[x][i]][j2][k2][l2]+yq[tl[v[x][i]]-1]);
//if(nex[j1][k2][0]==8)printf("???%d %d %d %d %d %d %d %d\n",x,j1,k1,l1,j2,k2,l2,dp[v[x][i]][j2][k2][l2]);
}
}
}
}
}
}
for(int j=0;j<=1;j++)
{
for(int k=0;k<=1;k++)
{
for(int l=0;l<=1;l++)
{
dp[x][j][k][l]=nex[j][k][l];
}
}
}
}
}
long long place_police(vector<int> P, vector<long long> C, vector<long long> W)
{
n=P.size()+1;
for(int i=0;i<n-1;i++)
{
v[P[i]+1].push_back(i+2);
qz[P[i]+1].push_back(C[i]);
}
dfs(1,0);
sort(yz+1,yz+cnt+1);
for(int i=1;i<=cnt;i++)yq[i]=W[i-1],yd[i]=dep[yz[i]];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=1;j++)
{
for(int k=0;k<=1;k++)
{
for(int l=0;l<=1;l++)
{
dp[i][j][k][l]=1000000000000000000LL;
}
}
}
}
//printf("orz\n");
solve(1,0);
long long ans=1000000000000000000LL;
for(int j=0;j<=1;j++)
{
for(int k=0;k<=1;k++)
{
for(int l=0;l<=1;l++)
{
ans=min(ans,dp[1][j][k][l]+yq[cnt]);
if(j==1&&k==1&&(yd[cnt]+yd[1])%2==0)continue;
if(l==1&&cnt%2==1)continue;
//printf("%d %d %d %lld\n",j,k,l,dp[1][j][k][l]);
ans=min(ans,dp[1][j][k][l]);
}
}
}
return ans;
}
詳細信息
cc1plus: fatal error: implementer.cpp: No such file or directory compilation terminated.