Submission #1141785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141785		nuutsnoynton	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	67 ms	12988 KiB

2016_ho_t3

#include <iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<deque>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<numeric>
#include<bitset>
#include<iomanip>
#include<cstdlib>
#include<time.h>
#include <functional>
#include <chrono>
#include <thread>
#include <fstream>
#include <random>

using namespace std;

#ifdef _DEBUG
#define prnt(a) cout<<#a<<"="<<a<<endl
#else
#define prnt(a) (void)0
#endif // _DEBUG

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#define ull unsigned long long
#define ll int
#define ld long double
#define INF (1LL<<30)
#define INFLL (1LL<<60)
#define MOD 1000000007
#define MOD2 998244353
#define rep(i,st,en) for(ll i=(st);i<(en);++i)
#define vld vector<ld>
#define vll	vector<ll>
#define vvll	vector<vll>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define pii	pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define VS vector<string>
#define MY_PI           3.141592653589793238462643383279502884L
#define all(v) (v).begin(), (v).end()

#define rd(...) __VA_ARGS__; read(__VA_ARGS__)
#define rdv(value,...) value(__VA_ARGS__);cin >> value
template <class T> auto& operator>>(istream& is, vector<T>& xs) {
	for (auto& x : xs) is >> x;
	return is;
}
template <class T> auto& operator<<(ostream& os, vector<T>& xs) {
	int sz = xs.size();
	rep(i, 0, sz) os << xs[i] << " \n"[i + 1 == sz];
	return os;
}
template <class T, class Y> auto& operator<<(ostream& os, pair<T, Y>& xs) {
	os << "{" << xs.first << ", " << xs.second << "}";
	return os;
}
template <class T, class Y> auto& operator>>(istream& is, vector<pair<T, Y>>& xs) {
	for (auto& [x1, x2] : xs) is >> x1 >> x2;
	return is;

}
template <class  ...Args>
auto& read(Args & ...args) { return (cin >> ... >> args); }

#define write(...) writemy(__VA_ARGS__);cout<<"\n"
void writemy() {}
template <typename Head, class  ...Args>
void writemy(const Head& head, const Args & ...args) {
	cout << head << " ";
	writemy(args...);
}

const ll M = 2e5 + 2;
const ll N = 1e5 + 2;
ll x[M], y[M], a[M];
int d[N], D[N];
vector < ll > adj[N];
ll used[M] = { 0 };
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n, m, r, i, j, x1, y1, s, ans, t;

	cin >> n >> m >> t;
	for (i = 1; i <= n; i++) {
		D[i] = 1e9;
		d[i] = 1e9;
	}
	D[1] = 0;

	for (i = 1; i <= m; i++) {
		cin >> x[i] >> y[i];
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	queue < ll > q;
	q.push(1);
	r = 0;
	while (!q.empty()) {
		x1 = q.front();
		r++;
		q.pop();
		for (ll X : adj[x1]) {
			if (D[X] <= D[x1] + 1)  continue;
			D[X] = D[x1] + 1;
			q.push(X);
		}
	}
	for (i = 1; i <= n; i++) {
		d[i] = D[i];
		D[i] = 1e9;
		adj[i].clear();
	}
	D[1] = 0;
	for (i = 1; i <= t; i++) {
		cin >> a[i];
		used[a[i]] = 1;
	}

	for (i = 1; i <= m; i++) {
		if (used[i] == 0) {
			if (d[x[i]] == d[y[i]] + 1) {
				adj[y[i]].push_back(x[i]);
			}
			if (d[y[i]] == d[x[i]] + 1) {
				adj[x[i]].push_back(y[i]);
			}
		}
	}
	q.push(1);
	while (!q.empty()) {
		x1 = q.front();
		q.pop();
		for (ll X : adj[x1]) {
			if (D[X] <= D[x1] + 1)  continue;
			D[X] = D[x1] + 1;
			q.push(X);
		}
	}
	s = 0;
	for (i = 1; i <= n; i++) {
		if (d[i] != 1e9 && d[i] == D[i]) s++;
	}

	vector < ll > Ans;
	for (i = t; i >= 1; i--) {
		Ans.push_back(r - s);
		x1 = x[a[i]];
		y1 = y[a[i]];
		if (d[x1] < d[y1])
			swap(x1, y1);
		//d[x1]>d[y1]
		if (abs(d[x1] - d[y1]) == 1) {
			adj[y1].push_back(x1);
		}
		if (d[x1]!=D[x1] && d[y1]==D[y1] && d[x1] == d[y1] + 1) {
			D[x1] = d[x1];
			s++;
			q.push(x1);
		}
		while (!q.empty()) {
			x1 = q.front();
			q.pop();
			for (ll X : adj[x1]) {
				if (D[X] == d[X]) continue;
				D[X] = min(D[x1] + 1, D[X]);
				if (D[X] == d[X]) {
					s++;
					q.push(X);
				}
			}
		}

	}
	reverse(Ans.begin(), Ans.end());
	for (i = 0; i < Ans.size(); i++) {
		cout << Ans[i] << "\n";
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39