oj.uz

답안 #1101353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1101353 2024-10-16T06:58:49 Z hungeazy Hotspot (NOI17_hotspot) C++17
0 / 100
 11 ms 24660 KB 
/*
* @Author: hungeazy
* @Date:   2024-10-16 13:45:49
* @Last Modified by:   hungeazy
* @Last Modified time: 2024-10-16 13:57:05
*/
#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 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 ""
#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 sub12 {

	int f[N],f2[N],d[N];

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

	void Dijkstra(int p, int end, int f[])
	{
		FOR(i,1,n) d[i] = oo;
		d[p] = 0;
		queue<int> q;
		q.push(p);
		maximize(f[p],1LL);
		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)
	{
		int ans = -oo;
		while (k--)
		{
			int a,b;
			cin >> a >> b;
			FOR(i,1,n)
			{
				Dijkstra(a,i,f);
				Dijkstra(i,b,f);
				Dijkstra(a,b,f2);
				maximize(ans,f[b]/f2[b]);
			}
		}
		cout << ans;
	}
	
}

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 (sub12::approved()) sub12::solve();
    time();
    return 0;
}
// ██░ ██  █    ██  ███▄    █   ▄████
//▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
//▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
//░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
//░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
// ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
// ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
// ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
// ░  ░  ░   ░              ░       ░

Compilation message

hotspot.cpp: In function 'int main()':
hotspot.cpp:111:13: 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:13: 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);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 24660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 24660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 24660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 24660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 24660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 24660 KB Output isn't correct
2 Halted 0 ms 0 KB -