QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396301#7077. Sheep VillagezhouhuanyiWA 2ms12748kbC++141.7kb2024-04-22 17:16:012024-04-22 17:16:01

Judging History

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

  • [2024-04-22 17:16:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12748kb
  • [2024-04-22 17:16:01]
  • 提交

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'