# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
707599 | bin9638 | Two Transportations (JOI19_transportations) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#ifndef SKY
#include "Azer.h"
#endif // SKY
using namespace std;
#define N 2010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
int n,dem=0,kq[N];
vector<ii>g[N];
#ifdef SKY
void SendA(bool y)
{
cout<<y<<endl;
}
#endif // SKY
void InitA(int cc, int A, vector<int> U, vector<int> V, vector<int> C)
{
n=cc;
for(int i=0;i<A;i++)
{
int u=U[i],v=V[i],L=C[i];
g[u].pb({L,v});
g[v].pb({L,u});
//cout<<u<<" "<<v<<" "<<L<<endl;
}
}
void ReceiveA(bool x)
{
if(x==1)
kq[dem/20]+=(1<<(dem%20));
dem++;
}
vector<int> Answer()
{
vector<int> ans(n);
for(int i=0;i<n;i++)
ans[i]=kq[i];
return ans;
}
#ifdef SKY
int main()
{
freopen("Azer.inp","r",stdin);
freopen("Azer.out","w",stdout);
int n,A;
vector<int>U,V,C;
cin>>n>>A;
for(int i=0;i<A;i++)
{
int u,v,c;
cin>>u>>v>>c;
U.pb(u);
V.pb(v);
C.pb(c);
}
InitA(n,A,U,V,C);
for(int i=0;i<80;i++)
{
int x;
cin>>x;
ReceiveA(x);
}
vector<int>ans=Answer();
for(int i=0;i<n;i++)cout<<ans[i]<<endl;
}
#endif // SKY
#include<bits/stdc++.h>
#ifndef SKY
#include "Azer.h"
#endif // SKY
using namespace std;
#define N 2010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
int n,dp[N],ktr[N];
vector<ii>g[N];
#ifdef SKY
void SendB(bool y)
{
cout<<y<<endl;
}
#endif // SKY
void InitB(int cc, int A, vector<int> U, vector<int> V, vector<int> C)
{
n=cc;
for(int i=0;i<A;i++)
{
int u=U[i],v=V[i],L=C[i];
g[u].pb({L,v});
g[v].pb({L,u});
//cout<<u<<" "<<v<<" "<<L<<endl;
}
priority_queue<ii>s;
memset(dp,0x3f3f,sizeof(dp));
dp[0]=0;
s.push({0,0});
while(!s.empty())
{
ii cc=s.top();
s.pop();
int u=cc.sc,L=-cc.fs;
if(ktr[u]==1)
continue;
ktr[u]=0;
for(auto v:g[u])
if(dp[v.sc]>L+v.fs)
{
dp[v.sc]=L+v.fs;
s.push({-dp[v.sc],v.sc});
}
}
for(int i=0;i<n;i++)
for(int j=0;j<20;j++)
SendB((dp[i]>>j)&1);
}
void ReceiveB(bool x)
{
}
#ifdef SKY
int main()
{
freopen("Baijan.inp","r",stdin);
freopen("Baijan.out","w",stdout);
int n,A;
vector<int>U,V,C;
cin>>n>>A;
for(int i=0;i<A;i++)
{
int u,v,c;
cin>>u>>v>>c;
U.pb(u);
V.pb(v);
C.pb(c);
}
InitB(n,A,U,V,C);
}
#endif // SKY