oj.uz

Submission #197128

# Submission time Handle Problem Language Result Execution time Memory
197128 2020-01-19T06:48:14 Z arnold518 Toll (BOI17_toll) C++14
7 / 100
 175 ms 21296 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e4;
const ll INF = 1e15;

int K, N, M, Q;
map<int, ll> adj[MAXN+10];

struct Node
{
	vector<vector<ll>> V;
	Node() { V=vector<vector<ll>>(K, vector<ll>(K, INF)); }
};
Node Z;

Node operator + (const Node &p, const Node &q)
{
	Node ret=Node();
	int i, j, k;
	for(i=0; i<K; i++)
	{
		for(j=0; j<K; j++)
		{
			ll val=INF;
			for(k=0; k<K; k++) val=min(val, p.V[i][k]+q.V[k][j]);
			ret.V[i][j]=val;
		}
	}
	return ret;
}

Node tree[MAXN*4+10];

void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		int i, j;
		tree[node]=Node();
		for(i=0; i<K; i++) for(j=0; j<K; j++)
		{
			int p=(tl-1)*K+i, q=tl*K+j;
			if(adj[p].find(q)!=adj[p].end()) tree[node].V[i][j]=adj[p][q];
		}
		//printf("%d %d : \n", tl, tr);
		//for(i=0; i<K; i++) { for(j=0; j<K; j++) printf("%lld ", tree[node].V[i][j]); printf("\n"); }
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	tree[node]=tree[node*2]+tree[node*2+1];
	int i, j;
	//printf("%d %d : \n", tl, tr);
	//for(i=0; i<K; i++) { for(j=0; j<K; j++) printf("%lld ", tree[node].V[i][j]); printf("\n"); }
}

Node query(int node, int tl, int tr, int l, int r)
{
	if(l<=tl && tr<=r) return tree[node];
	if(tr<l || r<tl) return Z;
	int mid=tl+tr>>1;
	return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r);
}

int main()
{
	int i, j;
	scanf("%d%d%d%d", &K, &N, &M, &Q);
	N=(N+K-1)/K*K;

	Z=Node();
	for(i=0; i<K; i++) Z.V[i][i]=0;

	for(i=1; i<=M; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u][v]=w;
	}

	init(1, 1, N/K-1);
	while(Q--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		if(a/K==b/K) { printf("-1"); continue; }
		Node t=query(1, 1, N/K-1, a/K+1, b/K);
		ll ans=t.V[a%K][b%K];
		if(ans==INF) ans=-1;
		printf("%lld\n", ans);
	}
}

Compilation message

toll.cpp: In function 'void init(int, int, int)':
toll.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
toll.cpp:58:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j;
      ^
toll.cpp:58:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
toll.cpp: In function 'Node query(int, int, int, int, int)':
toll.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
toll.cpp: In function 'int main()':
toll.cpp:73:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
toll.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &K, &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 17784 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 9 ms 7420 KB Output is correct
4 Correct 10 ms 7316 KB Output is correct
5 Correct 15 ms 7672 KB Output is correct
6 Correct 15 ms 7544 KB Output is correct
7 Correct 14 ms 7544 KB Output is correct
8 Correct 149 ms 17752 KB Output is correct
9 Correct 149 ms 17656 KB Output is correct
10 Correct 111 ms 13952 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 21296 KB Output is correct
2 Correct 11 ms 7416 KB Output is correct
3 Incorrect 12 ms 7416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7388 KB Output is correct
2 Incorrect 14 ms 7416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7388 KB Output is correct
2 Incorrect 14 ms 7416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 17784 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 9 ms 7420 KB Output is correct
4 Correct 10 ms 7316 KB Output is correct
5 Correct 15 ms 7672 KB Output is correct
6 Correct 15 ms 7544 KB Output is correct
7 Correct 14 ms 7544 KB Output is correct
8 Correct 149 ms 17752 KB Output is correct
9 Correct 149 ms 17656 KB Output is correct
10 Correct 111 ms 13952 KB Output is correct
11 Correct 165 ms 21296 KB Output is correct
12 Correct 11 ms 7416 KB Output is correct
13 Incorrect 12 ms 7416 KB Output isn't correct
14 Halted 0 ms 0 KB -