제출 #307044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
307044		arwaeystoamneg	Toll (BOI17_toll)	C++17	0 / 100	306 ms	135420 KiB

toll

/*
ID: awesome35
LANG: C++14
TASK: twofive
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
#define ednl '\n'
#define test int t;cin>>t;while(t--)
#define pq priority_queue
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const int inf = 1000000007;//998244353
const ld pi = 3.1415926535;


ll maximum(ll x, ll y)
{
	if (x > y)
		return x;
	return y;
}
ll minimum(ll x, ll y)
{
	if (x < y)
		return x;
	return y;
}
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, a.size()) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, a.size()) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
/*
void dijkstra(int i)
{//Preconditions for this to work: 1. no negative edges. 2. dist and parents are both initialized with size N and full of INT_MAX and 0 respectively while dist[i]=0 and parent[i]=-1
	priority_queue<pii>todo;
	vi finalized;
	finalized.rsz(N + 1, 0);//make sure that the size of adjacency is N+1
	todo.push(mp(0, i));
	while (!todo.empty())
	{//.s is indexs while .f is weight
		pii temp = todo.top();
		int indexs = temp.second;
		todo.pop();
		if (finalized[indexs])continue;
		finalized[indexs] = 1;
		trav(x, adjacency[indexs])
		{
			if (finalized[x.first])
				continue;
			if (dist[x.f] > x.s + dist[indexs])
			{
				dist[x.first] = x.second + dist[indexs];
				parents[x.f] = indexs;
				todo.push(mp(-dist[x.first], x.f));
			}
		}
	}
}
void build_primes()
{
	primes.reserve(50000);
	vi visited;
	visited.rsz(200000, 0);
	FOR(i, 2, 200000)
	{
		if (visited[i] == 0)
		{
			primes.pb(i);
			a = i;
			while (a < 200000)
			{
				visited[a] = 1;
				a += i;
			}
		}
	}
}
//Prim's Algorithm
// need vector<vpi>adjacency
ll prim()
{
	ll a = 0;
	vi visited;
	visited.rsz(n, 0);
	visited[0] = 1;
	pq<pii>todo;
	trav(x, adjacency[0])
		todo.push({ -x.s,x.f });
	F0R(i, n - 1)
	{
		pii temp = todo.top();
		todo.pop();
		int indexs = temp.s;
		if (visited[indexs])cont;
		a -= temp.f;
		visited[indexs] = 1;
		trav(x, adjacency[indexs])
			if (visited[x.f] == 0)
			{
				todo.push({ -x.s,x.f });
			}
	}
	return a;
}
vector<vector<ll>> matrix_mult(vector<vector<ll>>& a, vector<vector<ll>>& b)
{
	int n = a.size();
	vector<vector<ll>> answer;
	answer.resize(n);
	for (int i = 0; i < n; i++) answer[i].resize(n, 0);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) // calculate answer[i][j]
		{
			for (int k = 0; k < n; k++)
				answer[i][j] = (answer[i][j] + a[i][k] * b[k][j]) % inf;
		}
	}
	return answer;
}
vector<vector<ll>> matrix_exp(vector<vector<ll>>& a, ll n)
{
	vector<vector<ll>> result;
	result.resize(a.size());

	for (int i = 0; i < a.size(); i++)
	{
		result[i].resize(a[0].size(), 0);
		result[i][i] = 1;
	}
	while (n != 0)
	{
		if (n & 1)
			result = matrix_mult(result, a);
		a = matrix_mult(a, a);
		n = n >> 1;
	}
	return result;
}
// Union-Find
int find(int a) // return the root for node a
{
	if (a == links[a])
		return a;
	return links[a] = find(links[a]);
}
bool same(int a, int b) // check if node a and b has the same root
{
	return find(a) == find(b);
}
void unite(int a, int b)
{
	a = find(a);
	b = find(b);
	if (sizes[a] < sizes[b]) swap(a, b);
	sizes[a] += sizes[b]; //a always bigger than b, move subtree b under a
	links[b] = a;
}
ll get_flow(vector<vll>adj, int x, int y, int n)
{
	ll ans = 0;
	while (1)
	{
		vll dist(n), visited(n), parents(n, -1);
		dist[x] = linf;
		pq<pair<ll, ll>>todo; todo.push({ linf,x });
		while (todo.size())
		{
			pair<ll, ll> temp = todo.top(); todo.pop();
			F0R(i, n)
			{
				if (dist[i] < min(temp.f, adj[temp.s][i]))
				{
					dist[i] = min(temp.f, adj[temp.s][i]);
					parents[i] = temp.s;
					todo.push({ dist[i],i });
				}
			}
		}
		if (dist[y] == 0)break;
		ans += dist[y];
		int index = y;
		while (index != x)
		{
			adj[parents[index]][index] -= dist[y];
			adj[index][parents[index]] += dist[y];
			index = parents[index];
		}
	}
	return ans;
}
*/
int modInverse(int a, int m)
{
	int m0 = m;
	int y = 0, x = 1;

	if (m == 1)
		return 0;

	while (a > 1)
	{
		// q is quotient 
		int q = a / m;
		int t = m;

		// m is remainder now, process same as 
		// Euclid's algo 
		m = a % m, a = t;
		t = y;

		// Update y and x 
		y = x - q * y;
		x = t;
	}

	// Make x positive 
	if (x < 0)
		x += m0;

	return x;
}
ll power(ll x, ll y)
{
	ll k = 1 << 30;
	ll z = 1;
	while (k != 0)
	{
		z *= z;
		z %= inf;
		if (y >= k)
		{
			z *= x;
			z %= inf;
			y -= k;
		}
		k >>= 1;
	}
	return z;
}
// remember that you need to take abs
long double area(pii x, pii y, pii z)
{
	return ((ll)x.s * y.f + (ll)y.s * z.f + (ll)z.s * x.f - (ll)x.f * y.s - (ll)y.f * z.s - (ll)z.f * x.s) / 2.0;
}
bool clockwise(pii x, pii y, pii z)
{
	return area(x, y, z) > 0;
}
struct point
{
	ld x, y;
};
long double area(point x, point y, point z)
{
	return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(point x, point y, point z)
{
	return area(x, y, z) > 0;
}
int gcd(int a, int b)
{
	if (a > b)swap(a, b);
	if (a == 0)return b;
	return gcd(a, b % a);
}
int popcount(int a)
{
	int count = 0;
	while (a)
	{
		count += (a & 1);
		a >>= 1;
	}
	return count;
}
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
struct custom_hash_fast {
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		x ^= FIXED_RANDOM;
		return x ^ (x >> 16);
	}
};
ll choose(ll n, ll r)
{
	ll p = 1, k = 1;
	if (n - r < r)
		r = n - r;
	if (r != 0) {
		while (r) {
			p *= n;
			k *= r;
			long long m = gcd(p, k);
			p /= m;
			k /= m;
			n--;
			r--;
		}
	}
	else
		p = 1;
	return p;
}
//end of preprogrammed methods
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen((s + ".in").c_str(), "r", stdin);
	//freopen((s + ".out").c_str(), "w", stdout);
}
vector<vi> matrix_mult(vector<vi>& a, vector<vi>& b)
{
	int n = a.size();
	vector<vi> answer;
	answer.resize(n, vi(n, inf));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) // calculate answer[i][j]
		{
			for (int k = 0; k < n; k++)
				answer[i][j] = min(answer[i][j], a[i][k] + b[k][j]);
		}
	}
	return answer;
}
int k, n, q, m;
int main()
{
	setIO("gates");
	cin >> k >> n >> m >> q;
	n -= n % k;
	n += k;
	vector<vector<vi>>next;
	next.rsz(n / k, vector<vi>(k, vi(k, inf)));
	F0R(i, m)
	{
		int a, b, c; cin >> a >> b >> c;
		next[a / k][a % k][b % k] = c;
	}
	int log = 14;
	vector<vector<vector<vi>>>jump(n / k, vector<vector<vi>>(log, vector<vi>(k, vi(k))));
	F0R(i, n / k)jump[i][0] = next[i];
	F0R(i, log - 1)
	{
		F0R(j, n / k)
		{
			if (j + (1 << i + 1) < n / k)
			{
				jump[j][i + 1] = matrix_mult(jump[j][i], jump[j + (1 << i)][i]);
			}
		}
	}
	vector<vi>t(k, vi(k, inf));
	F0R(i, q)
	{
		int a, b; cin >> a >> b;
		int c = a / k, d = b / k;
		a %= k;
		b %= k;
		F0R(j, k)fill(all(t[j]), inf);
		F0R(j, k)t[j][j] = 0;
		int dist = d - c;
		int curr = log;
		while (curr)
		{
			if (dist & (1 << curr))
			{
				t = matrix_mult(t, jump[c][curr]);
				c += (1 << curr);
			}
			curr--;
		}
		cout << (t[a][b] == inf ? -1 : t[a][b]) << endl;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'void pv(std::vector<std::vector<int> >)':
toll.cpp:21:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
toll.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
toll.cpp:58:2: note: in expansion of macro 'F0R'
   58 |  F0R(i, a.size()) { cout << i << endl; pv(a[i]); cout << endl; }
      |  ^~~
toll.cpp: In function 'void pv(std::vector<std::vector<long long int> >)':
toll.cpp:21:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
toll.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
toll.cpp:59:26: note: in expansion of macro 'F0R'
   59 | }void pv(vector<vll>a) { F0R(i, a.size()) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
      |                          ^~~
toll.cpp: In function 'int main()':
toll.cpp:389:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  389 |    if (j + (1 << i + 1) < n / k)
      |                  ~~^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44