Submission #680854

#	Time	Username	Problem	Language	Result	Execution time	Memory
680854		alwaystle	Hotspot (NOI17_hotspot)	C++17	100 / 100	1649 ms	216096 KiB

hotspot

// Everything will be just tickety-boo!

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define forr(_a, _b, _c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a, _b, _c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a, _b, _c) for(_a = (_b); _a < (_c); ++_a)
#define mp make_pair
#define fi first
#define se second
#define vi vector
#define sz(_v) _v.begin(), _v.end()
#define mask(_x) (1ll << (_x))
#define bit(_x,_y) (((_x) >> (_y)) & 1)

const int N = 5e3 + 5;
int n, i, m, k, x, y, d[N][N], j, a[N], b[N];
vi<int> adj[N];
deque<int> st;
ll f[N][N];
bool dd[N];
pair<ld,int> o[N];
ld t1, t2;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	#ifdef umf
		freopen("test.inp","r",stdin);
		freopen("test.out","w",stdout);
	#endif

	cin >> n >> m;
	while(m--) {
		cin >> x >> y;
		++x;
		++y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	forr(i,1,n) {
		memset(dd,false,sizeof(dd));
		f[i][i] = 1;
		st.push_back(i);
		dd[i] = true;
		while(st.size()) {
			x = st.front();
			st.pop_front();
			forf(j,0,adj[x].size()) {
				y = adj[x][j];
				if(!dd[y]) {
					dd[y] = true;
					st.push_back(y);
					d[i][y] = d[i][x] + 1;
				}
				if(d[i][x] + 1 == d[i][y]) f[i][y] += f[i][x];
			}
		}
	}
	cin >> k;
	forr(i,1,k) {
		cin >> a[i] >> b[i];
		++a[i];
		++b[i];
	}
	forr(i,1,n) {
		o[i].se = i;
		forr(j,1,k) {
			if(d[a[j]][i] + d[i][b[j]] == d[a[j]][b[j]]) {
				t1 = f[a[j]][i] * f[i][b[j]];
				t2 = f[a[j]][b[j]];
				o[i].fi += t1 / t2;
			}
		}
	}
	sort(o + 1,o + 1 + n);
	cout << o[n].se - 1;

	return 0;
}

Compilation message (stderr)

hotspot.cpp: In function 'int main()':
hotspot.cpp:10:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define forf(_a, _b, _c) for(_a = (_b); _a < (_c); ++_a)
      |                                            ^
hotspot.cpp:51:4: note: in expansion of macro 'forf'
   51 |    forf(j,0,adj[x].size()) {
      |    ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 18 / 18
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36