| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1102909 |
2024-10-19T08:39:49 Z |
Cadoc |
Hotspot (NOI17_hotspot) |
C++14 |
|
1 ms |
4688 KB |
/*
Author: Cadocx
Codeforces: https://codeforces.com/profile/Kadoc
VNOJ: oj.vnoi.info/user/Cadoc
*/
#include <bits/stdc++.h>
using namespace std;
// input/output
#define fastIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define el cout << '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
// #pragma GCC optimize("O2", "unroll-loops", "Ofast")
// #pragma GCC target("avx,avx2,fma")
//data type
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define piv pair<int, vector<int>>
#define vi vector<int>
#define vl vector<ll>
#define vc vector<char>
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return 1; }; return 0; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return 1; }; return 0; }
//STL
#define sz(x) (int)(x).size()
#define FOR(i,l,r) for(auto i = l; i <= r; i++)
#define FORD(i,r,l) for(auto i = r; i >= l; i--)
#define forin(i,a) for(auto i : a)
#define pb push_back
#define eb emplace_back
#define pf push_front
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
//bitmask
#define bitcnt(n) __builtin_popcount(n)
#define mask(i) (1 << (i))
#define bit(n, i) (((n) >> (i)) & 1)
#define set_on(n, i) ((n) | mask(i))
#define set_off(n, i) ((n) & ~mask(i))
//constant
#define N 100005
#define MOD 1000230007
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define base 31
#define Kadoc 0
int n, m, q;
int d[2][N];
ll cnt[2][N];
long double f[N];
vector<int> g[N];
void ditcha(int d[], ll cnt[], int s){
queue<int> q;
FOR(i, 1, n) d[i] = -1;
d[s] = 0;
cnt[s] = 1;
q.push(s);
while(q.size()){
int u = q.front(); q.pop();
for(int v:g[u]){
if(d[v] < 0){
d[v] = d[u] + 1;
cnt[v] = cnt[u];
q.push(v);
}
else if(d[v] == d[u] + 1) cnt[v] += cnt[u];
}
}
}
void solve(){
cin >> n >> m;
FOR(i, 1, m){
int u, v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
cin >> q;
while(q--){
int u, v; cin >> u >> v;
ditcha(d[0], cnt[0], u);
ditcha(d[1], cnt[1], v);
FOR(i, 1, n) if(d[0][i] + d[1][i] == d[0][v]){
ll tot = cnt[0][u] * cnt[1][u];
f[i] += 1.0 * tot / cnt[0][v];
}
}
int Ans = -1;
FOR(i, 1, n) if(Ans < 0 || f[Ans] < f[i]) Ans = i;
cout << Ans;
}
int main(){
#define NAME "TASK"
if(fopen(NAME".inp", "r")){
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
fastIO;
if(Kadoc){
int tc; cin >> tc;
while(tc--){
solve();
}
} else solve();
}
Compilation message
hotspot.cpp: In function 'int main()':
hotspot.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen(NAME".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen(NAME".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
4688 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
4688 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
4688 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
4688 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
4688 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
4688 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
