oj.uz

Submission #1101689

# Submission time Handle Problem Language Result Execution time Memory
1101689 2024-10-16T15:27:08 Z hungeazy Hotspot (NOI17_hotspot) C++17
38 / 100
 12 ms 30800 KB 
/*
* @Author: hungeazy
* @Date:   2024-10-16 13:45:49
* @Last Modified by:   hungeazy
* @Last Modified time: 2024-10-16 22:26:58
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
// #pragma GCC optimize("O3")  
// #pragma GCC optimize("unroll-loops")  
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
using namespace std;
using namespace __gnu_pbds; 
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define ll long long 
#define lb long double 
#define ull unsigned long long
#define sz(x) x.size()
#define sqr(x) (1LL * (x) * (x))
#define all(x) x.begin(), x.end()
#define fill(f,x) memset(f,x,sizeof(f))
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define debug(x) cout << #x << " = " << x << '\n'
#define ii pair<int,int>
#define iii pair<int,ii>
#define di pair<ii,ii>
#define vi vector<int>
#define vii vector<ii>
#define mii map<int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define fi first
#define se second
#define pb push_back
#define MOD 1000000007
#define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define MASK(i) (1LL << (i))
#define c_bit(i) __builtin_popcountll(i)
#define BIT(x,i) ((x) & MASK(i))
#define SET_ON(x,i) ((x) | MASK(i))
#define SET_OFF(x,i) ((x) & ~MASK(i))
#define oo 1e18
#define name "TRAINCENTRE"
#define endl '\n'
#define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms.";
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
const int N = (int)1e6+10;
vi g[N];
int n,m,k;

namespace sub14 {

	int cnt[N],par[N],h[N];
	bool visited[N];

	bool approved()
	{
		return n <= 1e3 and m <= 1e3 and k <= 200;
	}

	void DFS(int u, int p)
	{
		visited[u] = true;
		par[u] = p;
		if (p != -1) h[u] = h[p]+1;
		for (int v : g[u])
			if (!visited[v])
				DFS(v,u);
	}

	void calc(int u, int v)
	{
		if (h[u] < h[v]) swap(u,v);
		while (h[u] > h[v])
		{
			cnt[u]++;
			u = par[u];
		}
		while (u != v)
		{
			cnt[u]++; cnt[v]++;
			u = par[u]; v = par[v];
		}
		cnt[u]++;
	}

	void solve(void)
	{
		DFS(0,-1);
		while (k--)
		{
			int a,b;
			cin >> a >> b;
			calc(a,b);
		}
		int u = 0;
		FOR(i,0,N-10)
			if (cnt[u] < cnt[i]) u = i;
		cout << u;
	}
	
}

namespace sub56 {

	int f[N],d[N];
	bool visited[N];
	lb cnt[N],ans[N];

	void BFS(int p)
	{
		FOR(i,0,n) d[i] = oo, visited[i] = false, cnt[i] = 0.0, f[i] = 0;
		queue<int> q;
		q.push(p);
		d[p] = 0; f[p] = 1;
		while (!q.empty())
		{
			int u = q.front();
			q.pop();
			for (int v : g[u])
				if (d[v] > d[u]+1) 
				{
					d[v] = d[u]+1;
					f[v] = f[u];
					q.push(v);
				}
				else if (d[v] == d[u]+1) f[v] += f[u];
		}
	}

	void solve(void)
	{
		while (k--)
		{
			int a,b;
			cin >> a >> b;
			BFS(a);
			int cur = f[b];
			if (cur != 0)
			{
				cnt[b] = 1.0L;
				queue<int> q;
				q.push(b);
				while (!q.empty())
				{
					int u = q.front();
					q.pop();
					if (visited[u]) continue;
					visited[u] = true;
					ans[u] += f[u];
					for (int v : g[u])
						if (d[v] == d[u]-1) 
						{
							q.push(v);
							cnt[v] += (f[v]*1.0/f[u]*1.0*cnt[u]);
						}
				}
			}
		}
		lb res = 0.0;
		int pos;
		FOR(i,0,n)
			if (res < ans[i]) res = ans[i], pos = i;
		cout << pos;
	}

}

signed main()
{
    fast;
    if (fopen(name".inp","r"))
    {
    	freopen(name".inp","r",stdin);
    	freopen(name".out","w",stdout);
    }
    cin >> n >> m;
    FOR(i,1,m)
    {
    	int u,v;
    	cin >> u >> v;
    	g[u].pb(v); g[v].pb(u);
    }
    cin >> k;
    if (sub14::approved()) sub14::solve();
    else sub56::solve();
    time();
    return 0;
}
// ██░ ██  █    ██  ███▄    █   ▄████
//▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
//▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
//░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
//░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
// ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
// ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
// ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
// ░  ░  ░   ░              ░       ░

Compilation message

hotspot.cpp: In function 'int main()':
hotspot.cpp:179:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |      freopen(name".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:180:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |      freopen(name".out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30544 KB Output is correct
2 Correct 12 ms 30544 KB Output is correct
3 Correct 9 ms 30544 KB Output is correct
4 Correct 9 ms 30288 KB Output is correct
5 Correct 12 ms 30544 KB Output is correct
6 Correct 9 ms 30544 KB Output is correct
7 Correct 11 ms 30544 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30544 KB Output is correct
2 Correct 12 ms 30544 KB Output is correct
3 Correct 9 ms 30544 KB Output is correct
4 Correct 9 ms 30288 KB Output is correct
5 Correct 12 ms 30544 KB Output is correct
6 Correct 9 ms 30544 KB Output is correct
7 Correct 11 ms 30544 KB Output is correct
8 Correct 12 ms 30412 KB Output is correct
9 Correct 9 ms 30544 KB Output is correct
10 Correct 9 ms 30408 KB Output is correct
11 Correct 9 ms 30460 KB Output is correct
12 Correct 8 ms 30288 KB Output is correct
13 Correct 10 ms 30544 KB Output is correct
14 Correct 10 ms 30544 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30544 KB Output is correct
2 Correct 12 ms 30544 KB Output is correct
3 Correct 9 ms 30544 KB Output is correct
4 Correct 9 ms 30288 KB Output is correct
5 Correct 12 ms 30544 KB Output is correct
6 Correct 9 ms 30544 KB Output is correct
7 Correct 11 ms 30544 KB Output is correct
8 Correct 9 ms 30544 KB Output is correct
9 Correct 9 ms 30408 KB Output is correct
10 Correct 8 ms 30544 KB Output is correct
11 Correct 9 ms 30544 KB Output is correct
12 Correct 9 ms 30288 KB Output is correct
13 Correct 8 ms 30288 KB Output is correct
14 Correct 8 ms 30544 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30544 KB Output is correct
2 Correct 12 ms 30544 KB Output is correct
3 Correct 9 ms 30544 KB Output is correct
4 Correct 9 ms 30288 KB Output is correct
5 Correct 12 ms 30544 KB Output is correct
6 Correct 9 ms 30544 KB Output is correct
7 Correct 11 ms 30544 KB Output is correct
8 Correct 12 ms 30412 KB Output is correct
9 Correct 9 ms 30544 KB Output is correct
10 Correct 9 ms 30408 KB Output is correct
11 Correct 9 ms 30460 KB Output is correct
12 Correct 8 ms 30288 KB Output is correct
13 Correct 10 ms 30544 KB Output is correct
14 Correct 10 ms 30544 KB Output is correct
15 Correct 9 ms 30544 KB Output is correct
16 Correct 9 ms 30408 KB Output is correct
17 Correct 8 ms 30544 KB Output is correct
18 Correct 9 ms 30544 KB Output is correct
19 Correct 9 ms 30288 KB Output is correct
20 Correct 8 ms 30288 KB Output is correct
21 Correct 8 ms 30544 KB Output is correct
22 Correct 8 ms 30544 KB Output is correct
23 Correct 8 ms 30488 KB Output is correct
24 Correct 8 ms 30544 KB Output is correct
25 Correct 9 ms 30544 KB Output is correct
26 Correct 8 ms 30544 KB Output is correct
27 Correct 8 ms 30288 KB Output is correct
28 Correct 8 ms 30544 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30544 KB Output is correct
2 Correct 12 ms 30544 KB Output is correct
3 Correct 9 ms 30544 KB Output is correct
4 Correct 9 ms 30288 KB Output is correct
5 Correct 12 ms 30544 KB Output is correct
6 Correct 9 ms 30544 KB Output is correct
7 Correct 11 ms 30544 KB Output is correct
8 Correct 12 ms 30412 KB Output is correct
9 Correct 9 ms 30544 KB Output is correct
10 Correct 9 ms 30408 KB Output is correct
11 Correct 9 ms 30460 KB Output is correct
12 Correct 8 ms 30288 KB Output is correct
13 Correct 10 ms 30544 KB Output is correct
14 Correct 10 ms 30544 KB Output is correct
15 Correct 6 ms 30544 KB Output is correct
16 Correct 6 ms 30544 KB Output is correct
17 Incorrect 8 ms 30800 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30544 KB Output is correct
2 Correct 12 ms 30544 KB Output is correct
3 Correct 9 ms 30544 KB Output is correct
4 Correct 9 ms 30288 KB Output is correct
5 Correct 12 ms 30544 KB Output is correct
6 Correct 9 ms 30544 KB Output is correct
7 Correct 11 ms 30544 KB Output is correct
8 Correct 12 ms 30412 KB Output is correct
9 Correct 9 ms 30544 KB Output is correct
10 Correct 9 ms 30408 KB Output is correct
11 Correct 9 ms 30460 KB Output is correct
12 Correct 8 ms 30288 KB Output is correct
13 Correct 10 ms 30544 KB Output is correct
14 Correct 10 ms 30544 KB Output is correct
15 Correct 9 ms 30544 KB Output is correct
16 Correct 9 ms 30408 KB Output is correct
17 Correct 8 ms 30544 KB Output is correct
18 Correct 9 ms 30544 KB Output is correct
19 Correct 9 ms 30288 KB Output is correct
20 Correct 8 ms 30288 KB Output is correct
21 Correct 8 ms 30544 KB Output is correct
22 Correct 8 ms 30544 KB Output is correct
23 Correct 8 ms 30488 KB Output is correct
24 Correct 8 ms 30544 KB Output is correct
25 Correct 9 ms 30544 KB Output is correct
26 Correct 8 ms 30544 KB Output is correct
27 Correct 8 ms 30288 KB Output is correct
28 Correct 8 ms 30544 KB Output is correct
29 Correct 6 ms 30544 KB Output is correct
30 Correct 6 ms 30544 KB Output is correct
31 Incorrect 8 ms 30800 KB Output isn't correct
32 Halted 0 ms 0 KB -