Submission #1123908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123908		vjudge	Aesthetic (NOI20_aesthetic)	C++20	35 / 100	339 ms	51384 KiB

Aesthetic

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define F first
#define S second
#define ALL(x) x.begin(),x.end()
#define random(l, r) (l + rand() % (r - l + 1))
#define int long long
#define maxn 300005
#define bit(x, i) ((x >> i) & 1)
#define pii pair<int, int>
#define MOD 1000000000000000007
#define Task "A"
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
struct edge {
	int v, w, p;
};
int n, m;
vector<edge> adj[maxn];
int a[maxn], b[maxn], w[maxn], p[maxn];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int d1[maxn], dn[maxn];
void dijkstra(int s, int* d) {
	for(int i = 1;i <= n;i++)d[i] = MOD;
	d[s] = 0;
	pq.push({0, s});
	while (!pq.empty()) {
		auto [l, u] = pq.top();
        pq.pop();
		if (l != d[u]) continue;
		for (edge e : adj[u]) {
            if(d[e.v] > l + e.w){
			   d[e.v] = l + e.w;
               pq.push({d[e.v], e.v});
			}
		}
	}
}
bool res;
int id[maxn], low[maxn], cnt,x;
void dfs(int u, int p) {
	id[u] = low[u] = cnt++;
	for (edge e : adj[u]) {
		if (e.v == p) continue;
		int maxx = min(d1[u] + dn[e.v], d1[e.v] + dn[u]) + e.w;
		if (maxx > x) continue;
		if (id[e.v] == -1) {
			dfs(e.v, u);
			if (res) return;
			low[u] = min(low[u], low[e.v]);
			if (low[e.v] > id[u] && maxx + e.p > x && id[n] != -1 && id[n] >= low[e.v])	{
                res = 1;
                return;
			}
		} else low[u] = min(low[u], id[e.v]);

	}
}

bool check(int x) {
	cnt = 0;
	::x = x;
	res = 0;
	memset(id, -1, sizeof (id));
	dfs(1, -1);
	return res;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 0;i < m;i++)cin >> a[i] >> b[i] >> w[i];
    int maxx = 0;
    for(int i = m - 1;i >= 0;i--){
        p[i] = maxx;
        maxx = max(maxx,w[i]);
    }
    for(int i = 0;i < m;i++) {
		adj[a[i]].push_back({b[i], w[i], p[i]});
		adj[b[i]].push_back({a[i], w[i], p[i]});
	}
    dijkstra(1, d1);
	dijkstra(n, dn);
	int l = d1[n], r = p[0] + d1[n] + 5;
	while (r - l > 1) {
		int mid = (l + r) / 2;

		if (check(mid)) l = mid;
		else r = mid;
	}
	cout << l + 1;
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27