oj.uz

답안 #307047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
307047 2020-09-26T20:35:32 Z arwaeystoamneg Toll (BOI17_toll) C++17
100 / 100
 328 ms 76456 KB 
/*
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 = 16;
	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 + 1)
		{
			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;
	}
}

Compilation message

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
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 75640 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 7 ms 1920 KB Output is correct
6 Correct 5 ms 1920 KB Output is correct
7 Correct 5 ms 1920 KB Output is correct
8 Correct 328 ms 76408 KB Output is correct
9 Correct 312 ms 76444 KB Output is correct
10 Correct 304 ms 75680 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 272 ms 64632 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 14 ms 1920 KB Output is correct
8 Correct 15 ms 1792 KB Output is correct
9 Correct 302 ms 76408 KB Output is correct
10 Correct 251 ms 58744 KB Output is correct
11 Correct 272 ms 66424 KB Output is correct
12 Correct 222 ms 57720 KB Output is correct
13 Correct 149 ms 34296 KB Output is correct
14 Correct 140 ms 35576 KB Output is correct
15 Correct 122 ms 33016 KB Output is correct
16 Correct 123 ms 33016 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 4 ms 1792 KB Output is correct
7 Correct 3 ms 1664 KB Output is correct
8 Correct 4 ms 1408 KB Output is correct
9 Correct 4 ms 1408 KB Output is correct
10 Correct 277 ms 75512 KB Output is correct
11 Correct 242 ms 66040 KB Output is correct
12 Correct 218 ms 58616 KB Output is correct
13 Correct 228 ms 58872 KB Output is correct
14 Correct 209 ms 58232 KB Output is correct
15 Correct 114 ms 33016 KB Output is correct
16 Correct 120 ms 32888 KB Output is correct

Subtask #4
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 4 ms 1792 KB Output is correct
7 Correct 3 ms 1664 KB Output is correct
8 Correct 4 ms 1408 KB Output is correct
9 Correct 4 ms 1408 KB Output is correct
10 Correct 277 ms 75512 KB Output is correct
11 Correct 242 ms 66040 KB Output is correct
12 Correct 218 ms 58616 KB Output is correct
13 Correct 228 ms 58872 KB Output is correct
14 Correct 209 ms 58232 KB Output is correct
15 Correct 114 ms 33016 KB Output is correct
16 Correct 120 ms 32888 KB Output is correct
17 Correct 252 ms 66252 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 8 ms 1920 KB Output is correct
24 Correct 7 ms 1664 KB Output is correct
25 Correct 9 ms 1536 KB Output is correct
26 Correct 9 ms 1536 KB Output is correct
27 Correct 300 ms 76456 KB Output is correct
28 Correct 234 ms 58744 KB Output is correct
29 Correct 238 ms 59128 KB Output is correct
30 Correct 221 ms 58360 KB Output is correct

Subtask #5
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 75640 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 7 ms 1920 KB Output is correct
6 Correct 5 ms 1920 KB Output is correct
7 Correct 5 ms 1920 KB Output is correct
8 Correct 328 ms 76408 KB Output is correct
9 Correct 312 ms 76444 KB Output is correct
10 Correct 304 ms 75680 KB Output is correct
11 Correct 272 ms 64632 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 14 ms 1920 KB Output is correct
18 Correct 15 ms 1792 KB Output is correct
19 Correct 302 ms 76408 KB Output is correct
20 Correct 251 ms 58744 KB Output is correct
21 Correct 272 ms 66424 KB Output is correct
22 Correct 222 ms 57720 KB Output is correct
23 Correct 149 ms 34296 KB Output is correct
24 Correct 140 ms 35576 KB Output is correct
25 Correct 122 ms 33016 KB Output is correct
26 Correct 123 ms 33016 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 0 ms 384 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 0 ms 384 KB Output is correct
32 Correct 4 ms 1792 KB Output is correct
33 Correct 3 ms 1664 KB Output is correct
34 Correct 4 ms 1408 KB Output is correct
35 Correct 4 ms 1408 KB Output is correct
36 Correct 277 ms 75512 KB Output is correct
37 Correct 242 ms 66040 KB Output is correct
38 Correct 218 ms 58616 KB Output is correct
39 Correct 228 ms 58872 KB Output is correct
40 Correct 209 ms 58232 KB Output is correct
41 Correct 114 ms 33016 KB Output is correct
42 Correct 120 ms 32888 KB Output is correct
43 Correct 252 ms 66252 KB Output is correct
44 Correct 1 ms 384 KB Output is correct
45 Correct 0 ms 384 KB Output is correct
46 Correct 1 ms 384 KB Output is correct
47 Correct 0 ms 384 KB Output is correct
48 Correct 1 ms 384 KB Output is correct
49 Correct 8 ms 1920 KB Output is correct
50 Correct 7 ms 1664 KB Output is correct
51 Correct 9 ms 1536 KB Output is correct
52 Correct 9 ms 1536 KB Output is correct
53 Correct 300 ms 76456 KB Output is correct
54 Correct 234 ms 58744 KB Output is correct
55 Correct 238 ms 59128 KB Output is correct
56 Correct 221 ms 58360 KB Output is correct
57 Correct 288 ms 59256 KB Output is correct
58 Correct 320 ms 76408 KB Output is correct
59 Correct 285 ms 66296 KB Output is correct