QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#396301 | #7077. Sheep Village | zhouhuanyi | WA | 2ms | 12748kb | C++14 | 1.7kb | 2024-04-22 17:16:01 | 2024-04-22 17:16:01 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 200000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int num,data,snum;
};
struct node
{
int num,data;
bool operator < (const node &t)const
{
return data<t.data;
}
};
node tong[N+1];
int n,m,k,length,depth[N+1],fa[N+1],tfa[N+1],dp[N+1];
long long ans;
vector<reads>E[N+1];
bool used[N+1],vis[N+1];
void add(int x,int y,int z,int w)
{
E[x].push_back((reads){y,z,w}),E[y].push_back((reads){x,z,w});
return;
}
void dfs(int x)
{
used[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i].num])
fa[E[x][i].num]=x,tfa[E[x][i].num]=E[x][i].data,depth[E[x][i].num]=depth[x]+1,vis[E[x][i].snum]=1,dfs(E[x][i].num),dp[x]+=dp[E[x][i].num];
return;
}
int main()
{
int x,y,z,cnt,scnt;
n=read(),m=read(),k=read();
for (int i=1;i<=k;++i) x=read(),dp[x]++;
for (int i=1;i<=k;++i) x=read(),dp[x]--;
for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),add(x,y,z,i);
depth[1]=1,dfs(1);
for (int i=1;i<=n;++i)
for (int j=0;j<E[i].size();++j)
if (!vis[E[i][j].snum]&&depth[i]<depth[E[i][j].num])
{
x=E[i][j].num,length=cnt=scnt=0;
while (x!=i) tong[++length]=(node){tfa[x],dp[x]},x=fa[x];
tong[++length]=(node){E[i][j].data,0},sort(tong+1,tong+length+1);
for (int k=1;k<=length;++k) cnt+=tong[k].num;
for (int k=1;k<=length;++k)
{
scnt+=tong[k].num;
if (scnt>=((cnt+1)>>1))
{
for (int t=1;t<=length;++t) ans+=1ll*tong[t].num*abs(tong[k].data-tong[t].data);
break;
}
}
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12600kb
input:
5 8 4 2 2 3 3 4 4 5 5 1 2 1 2 1 1 1 3 1 3 1 1 1 4 1 4 1 1 1 5 1 5 1 1
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 0ms
memory: 11928kb
input:
5 5 3 1 3 3 5 2 4 1 2 3 2 3 1 3 4 1 4 5 4 5 1 1
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 2ms
memory: 11980kb
input:
5 5 3 1 3 5 5 2 4 1 2 2 2 3 1 3 4 2 4 5 2 5 1 3
output:
4
result:
ok single line: '4'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 12748kb
input:
3 2 2 1 2 2 3 1 2 1 2 3 2
output:
0
result:
wrong answer 1st lines differ - expected: '3', found: '0'