oj.uz

Submission #308191

# Submission time Handle Problem Language Result Execution time Memory
308191 2020-09-30T08:47:10 Z arnold518 Two Transportations (JOI19_transportations) C++14
8 / 100
 683 ms 278532 KB 
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int MAXA = 6e5;
const int INF = 1e9;

struct Edge
{
    int u, v, w;
};

static int N, A, B;
static Edge EA[MAXA+10], EB[MAXA+10];
static int ans[MAXN+10];
static vector<pii> adj[MAXN+10];
static int cnt=0;
static int par[MAXN+10], len[MAXN+10];

struct Queue
{
    int u, w;
    bool operator < (const Queue &p) const
    {
        return w>p.w;
    }
};
static int dist[MAXN+10];


vector<int> Answer()
{
    vector<int> ret=vector<int>(ans, ans+N);
    return ret;
}

void InitA(int _N, int _A, vector<int> _U, vector<int> _V, vector<int> _C)
{
    N=_N; A=_A;
    for(int i=0; i<A; i++) EA[i]={_U[i], _V[i], _C[i]};
}

void dijk()
{
    //printf("B : %d\n", B);
    for(int i=0; i<A; i++)
    {
        int u=EA[i].u, v=EA[i].v, w=EA[i].w;
        assert(u!=v); assert(w<=500);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for(int i=0; i<N; i++)
    {
        int u=par[i], v=i, w=len[i];
        if(u==v) continue;
        assert(u!=v); assert(w<=500);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});   
    }

    for(int i=0; i<N; i++) dist[i]=INF;

    priority_queue<Queue> PQ;
    PQ.push({0, 0});

    while(!PQ.empty())
    {
        Queue now=PQ.top(); PQ.pop();
        if(dist[now.u]<=now.w) continue;
        //printf("%d %d\n", now.u, now.w);
        dist[now.u]=now.w;
        for(auto nxt : adj[now.u]) PQ.push({nxt.first, nxt.second+now.w});
    }
    for(int i=0; i<N; i++) ans[i]=dist[i];
}

void ReceiveA(bool x)
{
    if(x)
    {
        int t=cnt%20;
        if(t<11) par[cnt/20]|=(1<<t);
        else len[cnt/20]|=(1<<(t-11));
    }
    if(cnt==N*20-1) dijk();
    cnt++;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int MAXA = 5e5;
const int INF = 1e9;

struct Edge
{
    int u, v, w;
};

static int N, B;
static Edge EA[MAXA+10], EB[MAXA+10];
static int ans[MAXN+10];
static vector<pii> adj[MAXN+10];
static int cnt=0;

static int par[MAXN+10], len[MAXN+10];
static bool vis[MAXN+10];

void dfs(int now, int bef)
{
	par[now]=bef;
	vis[now]=true;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		len[nxt.first]=nxt.second;
		dfs(nxt.first, now);
	}
}

void InitB(int _N, int _B, vector<int> _U, vector<int> _V, vector<int> _C)
{
    N=_N; B=_B;
    for(int i=0; i<B; i++) EB[i]={_U[i], _V[i], _C[i]};
    for(int i=0; i<B; i++)
    {
    	int u=EB[i].u, v=EB[i].v, w=EB[i].w;
    	adj[u].push_back({v, w});
    	adj[v].push_back({u, w});
    }

    for(int i=0; i<N; i++)
    {
    	if(vis[i]) continue;
    	dfs(i, i);
    }

	for(int i=0; i<N; i++)
	{
		for(int j=0; j<11; j++)
		{
			if(par[i]&(1<<j)) SendB(1);
			else SendB(0);
		}
		for(int j=0; j<9; j++)
		{
			if(len[i]&(1<<j)) SendB(1);
			else SendB(0);
		}
	}
}

void ReceiveB(bool x)
{

}

Compilation message

Azer.cpp:19:26: warning: 'EB' defined but not used [-Wunused-variable]
   19 | static Edge EA[MAXA+10], EB[MAXA+10];
      |                          ^~
Azer.cpp:18:18: warning: 'B' defined but not used [-Wunused-variable]
   18 | static int N, A, B;
      |                  ^

Baijan.cpp:22:12: warning: 'cnt' defined but not used [-Wunused-variable]
   22 | static int cnt=0;
      |            ^~~
Baijan.cpp:20:12: warning: 'ans' defined but not used [-Wunused-variable]
   20 | static int ans[MAXN+10];
      |            ^~~
Baijan.cpp:19:13: warning: 'EA' defined but not used [-Wunused-variable]
   19 | static Edge EA[MAXA+10], EB[MAXA+10];
      |             ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 2264 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Memory limit exceeded 174 ms 278532 KB Unexpected end of file - int32 expected (Baijan)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1280 KB Output is correct
2 Correct 682 ms 2040 KB Output is correct
3 Memory limit exceeded 174 ms 278532 KB Unexpected end of file - int32 expected (Baijan)
4 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 1912 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 674 ms 2048 KB Output is correct
4 Correct 683 ms 1664 KB Output is correct
5 Correct 642 ms 1896 KB Output is correct
6 Correct 679 ms 1840 KB Output is correct
7 Correct 588 ms 2024 KB Output is correct
8 Correct 626 ms 1928 KB Output is correct
9 Correct 626 ms 1880 KB Output is correct
10 Correct 392 ms 1936 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 1536 KB Output is correct
2 Correct 288 ms 1936 KB Output is correct
3 Memory limit exceeded 272 ms 278532 KB Unexpected end of file - int32 expected (Baijan)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 1536 KB Output is correct
2 Correct 288 ms 1936 KB Output is correct
3 Memory limit exceeded 272 ms 278532 KB Unexpected end of file - int32 expected (Baijan)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 1536 KB Output is correct
2 Correct 288 ms 1936 KB Output is correct
3 Memory limit exceeded 272 ms 278532 KB Unexpected end of file - int32 expected (Baijan)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 2264 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Memory limit exceeded 174 ms 278532 KB Unexpected end of file - int32 expected (Baijan)
4 Halted 0 ms 0 KB -