Submission #1342660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342660		weedywelon	Computer Network (BOI14_network)	C++20	50 / 100	52 ms	4372 KiB

network

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#include "network.h"
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;

//n^2 get all edges 
//run bfs

//so u know all the dists from a 
//let dist from a to b be d
//categorise by distance to a
//2n: get all nodes that are along a shortest path
//fix the one u want to travel to
//for each x at distance, check whether prev is on a shortest path from a to x
//build the path

vector<int> d[1003]; //nodes that are on a shortest path from a to b that are d[i] from a
void findRoute (int N, int a, int b){
	int n=N;
	vector<PII> v(n+1);
	int dist=1e5;
	FR(i,1,n+1){
		if (i==a || i==b){
			v[i]=mp(1e5,1e5);
			continue;
		}
		v[i]=mp(ping(a,i)+1,ping(i,b)+1);
		dist=min(dist,v[i].A+v[i].B);
	}
	
	FR(i,1,n+1){
		if (v[i].A+v[i].B==dist) d[v[i].A].push_back(i); //on a shortest path
	}
	
	int cur=d[1][0];
	vector<int> path;
	path.push_back(cur);
	//construct a path containing cur
	FR(i,2,dist){
		for (int x:d[i]) if (ping(x,cur)==0){
			path.push_back(x);
			cur=x;
			break;
		}
	}
	path.push_back(b);
	for (int u:path) travelTo(u);
	return;
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:48:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf ("%d%d%d%d", &N, &a, &b, &M);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
grader.c:51:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |             scanf("%d", &distance[u][v]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 25