제출 #802134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802134		fatemetmhr	Seesaw (JOI22_seesaw)	C++17	0 / 100	4 ms	5204 KiB

seesaw

// Be name khode //


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) x.begin(), x.end()
#define mp     make_pair
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 1e5 + 5;
const ll  inf   = 1e18;

int n;
ll dis[maxn5], dis0[maxn5];
int per[maxn5];
vector <pair <int, int>> adj[maxn5];
set <pair<ll, int>> av;

bool cmp(int i, int j){return dis[i] < dis[j];}

void dij(int rt){
	fill(dis, dis + n + 5, inf);
	dis[rt] = 0;
	av.insert({0, rt});
	while(av.size()){
		int v = av.begin() -> se;
		av.erase(av.begin());
		for(auto p : adj[v]) if(dis[v] + p.se < dis[p.fi]){
			av.erase({dis[p.fi], p.fi});
			dis[p.fi] = p.se + dis[v];
			av.insert({dis[p.fi], p.fi});
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	int m; cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b, c; cin >> a >> b >> c;
		a--; b--;
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}
	dij(0);
	for(int i = 0; i < n; i++)
		dis0[i] = dis[i];
	dij(n - 1);
	ll len = dis[0];
	//cout << len << endl;
	bool re = false;
	for(int i = 0; i < n; i++){
		if(dis0[i] + dis[i] > len)
			re = true;
		//cout << i << ' ' << re << endl;
		for(auto p : adj[i]) if(dis[p.fi] < dis[i] && dis[p.fi] + p.se + dis0[i] > len)
			re = true;
		//cout << i << ' ' << re << endl;
		per[i] = i;
	}
	if(re)
		return cout << 1 << endl, 0;
	sort(per, per + n, cmp);
	int cur = 0;
	for(int i = 0; i < n; i++){
		int v = per[i];
		for(auto p : adj[v]) if(dis[p.fi] < dis[v])
			cur--;
		if(cur && v != 0){
			int cnt = 0;
			for(auto p : adj[v]) if(dis[p.fi] < dis[v])
				cnt++;
			if(cnt > 1)
				re = true;
			//cout << v << ' ' << cnt << ' ' << re << endl;
		}
		for(auto p : adj[v]) if(dis[p.fi] > dis[v])
			cur++;
	}
	cout << re << endl;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33