QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#720143	#67. Two Transportations	int_R	0	2ms	6164kb	C++20	3.4kb	2024-11-07 10:51:36	2024-11-07 10:51:36

Judging History

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

[2024-11-07 10:51:36]
评测

测评结果：0
用时：2ms
内存：6164kb

查看

[2024-11-07 10:51:36]
提交

Azer

#include "Azer.h"
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
typedef vector<int> V;

namespace A{
const int MAXN=2e3+10,MAXM=1e6+10;
int to[MAXM],nxt[MAXM],head[MAXN],val[MAXM],tot;
int o=1,n,r=11,tmp,dis[MAXN],pre,cnt,MIN,pos;bool vis[MAXN];

inline void add(int x,int y,int z)
	{to[++tot]=y,nxt[tot]=head[x],val[head[x]=tot]=z;}

inline void upd(int x,int D)
{
	++cnt,pre=dis[x]=D,vis[x]=true;
	for(int i=head[x];i;i=nxt[i])
		{int y=to[i];dis[y]=min(dis[y],dis[x]+val[i]);}
}

inline void find()
{
	MIN=1e9;for(int i=0;i<n;++i)
		if(!vis[i]&&dis[i]<MIN)
			MIN=dis[i],pos=i;
}

inline void Send(int k,int x)
	{for(int i=k-1;~i;--i) SendA((x>>i)&1);}

inline void send(bool flag)
	{find();flag?Send(9,min(MIN-pre,511)):Send(11,pos);}

inline void dij()
	{find();upd(pos,MIN);}

void Init(int n,int m,V x,V y,V z)
{
	A::n=n,o=1;
	for(int i=1;i<n;++i) dis[i]=(1<<20)-1;
	for(int i=0;i<m;++i) add(x[i],y[i],z[i]),add(y[i],x[i],z[i]);
}

void Receive(bool f)
{
	tmp=tmp<<1|f;if(--r) return ;
	if(o==1)
	{
		// cout<<'A'<<o<<' '<<tmp<<'\n';
		int x=tmp;tmp=0,upd(x,pre);
		if(cnt==n) return ;
		send(1),o=3,r=9;
	}
	else if(o==2)
	{
		// cout<<'A'<<o<<' '<<tmp<<'\n';
		int D=tmp;tmp=0;find(),send(1);
		if(D<=MIN-pre) pre+=D,o=1,r=11;
		else upd(pos,MIN),Send(11,pos),o=2,r=9;
	}
	else
	{
		// cout<<'A'<<o<<' '<<tmp<<'\n';
		int D=tmp;tmp=0;find();
		if(D<MIN-pre) pre+=D,o=1,r=11;
		else upd(pos,MIN),Send(11,pos),o=2,r=9;
	}
}

};

void InitA(int n,int m,V x,V y,V z)
{
	A::Init(n,m,x,y,z);
}

void ReceiveA(bool f)
{
	A::Receive(f);
}

V Answer(){V ans(A::n);for(int i=0;i<A::n;++i) ans[i]=A::dis[i];return ans;}

Source code, Language: C++20

Baijan

#include "Baijan.h"
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
typedef vector<int> V;

namespace B{
const int MAXN=2e3+10,MAXM=1e6+10;
int to[MAXM],nxt[MAXM],head[MAXN],val[MAXM],tot;
int o=2,n,r=9,tmp,dis[MAXN],pre,cnt,MIN,pos;bool vis[MAXN];

inline void add(int x,int y,int z)
	{to[++tot]=y,nxt[tot]=head[x],val[head[x]=tot]=z;}

inline void upd(int x,int D)
{
	++cnt,pre=dis[x]=D,vis[x]=true;
	for(int i=head[x];i;i=nxt[i])
		{int y=to[i];dis[y]=min(dis[y],dis[x]+val[i]);}
}

inline void find()
{
	MIN=1e9;for(int i=0;i<n;++i)
		if(!vis[i]&&dis[i]<MIN)
			MIN=dis[i],pos=i;
}

inline void Send(int k,int x)
	{for(int i=k-1;~i;--i) SendB((x>>i)&1);}

inline void send(bool flag)
	{find();flag?Send(9,min(MIN-pre,511)):Send(11,pos);}

inline void dij()
	{find();upd(pos,MIN);}

void Init(int n,int m,V x,V y,V z)
{
	B::n=n,o=2;
	for(int i=1;i<n;++i) dis[i]=(1<<20)-1;
	for(int i=0;i<m;++i) add(x[i],y[i],z[i]),add(y[i],x[i],z[i]);
	upd(0,0),Send(11,0);
}

void Receive(bool f)
{
	tmp=tmp<<1|f;if(--r) return ;
	if(o==1)
	{
		// cout<<'B'<<o<<' '<<tmp<<'\n';
		int x=tmp;tmp=0,upd(x,pre);
		if(cnt==n) return ;
		send(1),o=3,r=9;
	}
	else if(o==2)
	{
		// cout<<'B'<<o<<' '<<tmp<<'\n';
		int D=tmp;tmp=0;find(),send(1);
		if(D<=MIN-pre) pre+=D,o=1,r=11;
		else upd(pos,MIN),Send(11,pos),o=2,r=9;
	}
	else
	{
		// cout<<'B'<<o<<' '<<tmp<<'\n';
		int D=tmp;tmp=0;find();
		if(D<MIN-pre) pre+=D,o=1,r=11;
		else upd(pos,MIN),Send(11,pos),o=2,r=9;
	}
}

};

void InitB(int n,int m,V x,V y,V z)
{
	B::Init(n,m,x,y,z);
}

void ReceiveB(bool f)
{
	B::Receive(f);
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 2ms

memory: 5836kb

input:

-1

output:

-1
0 0 0 0 0 0 0 0 0 0 0 -1

input:

output:

result:

wrong answer 2nd lines differ - expected: '2417', found: '1048575'

Subtask #2:

score: 0

Wrong Answer

Test #7:

score: 8

Accepted

time: 0ms

memory: 3804kb

input:

-1

output:

-1
0 0 0 0 0 0 0 0 0 0 0 -1

input:

output:

result:

ok single line: '0'

Test #8:

score: 0

Wrong Answer

time: 1ms

memory: 5896kb

input:

-1

output:

-1
0 0 0 0 0 0 0 0 0 0 0 -1

input:

output:

result:

wrong answer 2nd lines differ - expected: '128264', found: '1048575'

Subtask #3:

score: 0

Wrong Answer

Test #14:

score: 0

Wrong Answer

time: 1ms

memory: 5924kb

input:

-1

output:

-1
0 0 0 0 0 0 0 0 0 0 0 -1

input:

output:

result:

wrong answer 2nd lines differ - expected: '3328', found: '1048575'

Subtask #4:

score: 0

Wrong Answer

Test #24:

score: 0

Wrong Answer

time: 0ms

memory: 5860kb

input:

-1

output:

-1
0 0 0 0 0 0 0 0 0 0 0 -1

input:

output:

result:

wrong answer 2nd lines differ - expected: '1881', found: '1048575'

Subtask #5:

score: 0

Wrong Answer

Test #38:

score: 0

Wrong Answer

time: 0ms

memory: 5852kb

input:

-1

output:

-1
0 0 0 0 0 0 0 0 0 0 0 -1

input:

output:

result:

wrong answer 2nd lines differ - expected: '3467', found: '1048575'

Subtask #6:

score: 0

Wrong Answer

Test #51:

score: 0

Wrong Answer

time: 0ms

memory: 6164kb

input:

-1

output:

-1
0 0 0 0 0 0 0 0 0 0 0 -1

input:

output:

result:

wrong answer 2nd lines differ - expected: '4745', found: '1048575'

Subtask #7:

score: 0

Wrong Answer

Test #64:

score: 0

Wrong Answer

time: 0ms

memory: 6016kb

input:

-1

output:

-1
0 0 0 0 0 0 0 0 0 0 0 -1

input:

output:

result:

wrong answer 2nd lines differ - expected: '25855', found: '1048575'