답안 #58222

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58222 2018-07-17T08:22:02 Z 김세빈(#1689) Wild Boar (JOI18_wild_boar) C++11
12 / 100
120 ms 110868 KB
#include <bits/stdc++.h>

using namespace std;

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

const ll sz = 100;

struct path{
	ll s, e, v;
	path() {}
	path(ll _v, ll _s, ll _e) { s = _s, e = _e, v = _v; }
	bool operator< (const path& p) const { return v > p.v; }
};

typedef vector <path> vp;

vp T[303030];
priority_queue <path> Q;
vp K[2020][2020];
vector <pll> V[2020];
bool chk[2020][2020];
ll L[101010];
ll n, m, k;

vp add(vp &a, vp &b)
{
	vp ret;
	
	for(auto &p1: a){
		for(auto &p2 : b){
			if(p1.e != p2.s){
				ret.push_back(path(p1.v + p2.v, p1.s, p2.e));
			}
		}
	}
	
	if(!ret.empty()){
		sort(ret.begin(), ret.end());
		reverse(ret.begin(), ret.end());
		for(;ret.size() > sz;) ret.pop_back();
	}
	
	return ret;
}

void dijkstra(ll a, ll b, ll v)
{
	path p;
	ll i;
	
	chk[a][b] = 1;
	
	Q.push(path(v, a, b));
	
	for(;!Q.empty();){
		p = Q.top(); Q.pop();
		if(chk[p.e][p.s]) continue;
		
		chk[p.e][p.s] = 1;
		K[a][p.e].push_back(path(p.v, b, p.s));
		
		for(pll &j: V[p.e]){
			if(!chk[j.first][p.e] && j.first != p.s){
				Q.push(path(p.v + j.second, p.e, j.first));
			}
		}
	}
	
	for(i=1;i<=n;i++) for(pll &j: V[i]){
		chk[i][j.first] = 0;
	}
}

void init_seg(ll p, ll s, ll e)
{
	if(s == e){
		T[p] = K[L[s]][L[s+1]];
		return;
	}
	
	init_seg(p<<1, s, (s+e>>1));
	init_seg(p<<1|1, (s+e>>1)+1, e);
	
	T[p] = add(T[p<<1], T[p<<1|1]);
}

void update(ll p, ll s, ll e, ll v)
{
	if(s == e){
		T[p] = K[L[s]][L[s+1]];
		return;
	}
	
	if(v <= (s+e>>1)) update(p<<1, s, (s+e>>1), v);
	else update(p<<1|1, (s+e>>1)+1, e, v);
	
	T[p] = add(T[p<<1], T[p<<1|1]);
}

int main()
{
	ll i, j, q, a, b, c;
	path p;
	
	scanf("%lld%lld%lld%lld", &n, &m, &q, &k);
	
	for(i=1;i<=m;i++){
		scanf("%lld%lld%lld", &a, &b, &c);
		V[a].push_back(pll(b, c));
		V[b].push_back(pll(a, c));
	}
	
	for(i=1;i<=n;i++) for(pll &t: V[i]){
		dijkstra(i, t.first, t.second);
	}
	
	for(i=1;i<=n;i++) for(j=1;j<=n;j++){
		if(!K[i][j].empty()){
			sort(K[i][j].begin(), K[i][j].end());
			reverse(K[i][j].begin(), K[i][j].end());
			for(;K[i][j].size() > sz;) K[i][j].pop_back();
		}
	}
	
	for(i=1;i<=k;i++){
		scanf("%lld", L+i);
	}
	
	init_seg(1, 1, k-1);
	
	for(;q--;){
		scanf("%lld%lld", &a, &b);
		L[a] = b;
		if(a < k) update(1, 1, k-1, a);
		if(a > 1) update(1, 1, k-1, a-1);
		
		if(T[1].empty()) printf("-1\n");
		else printf("%lld\n", T[1][0].v);
	}
	
	return 0;
}

Compilation message

wild_boar.cpp: In function 'void init_seg(ll, ll, ll)':
wild_boar.cpp:83:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  init_seg(p<<1, s, (s+e>>1));
                     ~^~
wild_boar.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  init_seg(p<<1|1, (s+e>>1)+1, e);
                    ~^~
wild_boar.cpp: In function 'void update(ll, ll, ll, ll)':
wild_boar.cpp:96:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= (s+e>>1)) update(p<<1, s, (s+e>>1), v);
           ~^~
wild_boar.cpp:96:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= (s+e>>1)) update(p<<1, s, (s+e>>1), v);
                                     ~^~
wild_boar.cpp:97:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else update(p<<1|1, (s+e>>1)+1, e, v);
                       ~^~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld", &n, &m, &q, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", L+i);
   ~~~~~^~~~~~~~~~~~~
wild_boar.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 103288 KB Output is correct
2 Correct 92 ms 104304 KB Output is correct
3 Correct 107 ms 104568 KB Output is correct
4 Correct 108 ms 104568 KB Output is correct
5 Correct 92 ms 104568 KB Output is correct
6 Correct 91 ms 104568 KB Output is correct
7 Correct 89 ms 104568 KB Output is correct
8 Correct 90 ms 104568 KB Output is correct
9 Correct 115 ms 104568 KB Output is correct
10 Correct 98 ms 104568 KB Output is correct
11 Correct 88 ms 104568 KB Output is correct
12 Correct 120 ms 104568 KB Output is correct
13 Correct 94 ms 104568 KB Output is correct
14 Correct 90 ms 104568 KB Output is correct
15 Correct 105 ms 104568 KB Output is correct
16 Correct 103 ms 104568 KB Output is correct
17 Correct 117 ms 104568 KB Output is correct
18 Correct 88 ms 104568 KB Output is correct
19 Correct 87 ms 104568 KB Output is correct
20 Correct 88 ms 104568 KB Output is correct
21 Correct 92 ms 104568 KB Output is correct
22 Correct 109 ms 104604 KB Output is correct
23 Correct 115 ms 104604 KB Output is correct
24 Correct 109 ms 104604 KB Output is correct
25 Correct 93 ms 104624 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 103288 KB Output is correct
2 Correct 92 ms 104304 KB Output is correct
3 Correct 107 ms 104568 KB Output is correct
4 Correct 108 ms 104568 KB Output is correct
5 Correct 92 ms 104568 KB Output is correct
6 Correct 91 ms 104568 KB Output is correct
7 Correct 89 ms 104568 KB Output is correct
8 Correct 90 ms 104568 KB Output is correct
9 Correct 115 ms 104568 KB Output is correct
10 Correct 98 ms 104568 KB Output is correct
11 Correct 88 ms 104568 KB Output is correct
12 Correct 120 ms 104568 KB Output is correct
13 Correct 94 ms 104568 KB Output is correct
14 Correct 90 ms 104568 KB Output is correct
15 Correct 105 ms 104568 KB Output is correct
16 Correct 103 ms 104568 KB Output is correct
17 Correct 117 ms 104568 KB Output is correct
18 Correct 88 ms 104568 KB Output is correct
19 Correct 87 ms 104568 KB Output is correct
20 Correct 88 ms 104568 KB Output is correct
21 Correct 92 ms 104568 KB Output is correct
22 Correct 109 ms 104604 KB Output is correct
23 Correct 115 ms 104604 KB Output is correct
24 Correct 109 ms 104604 KB Output is correct
25 Correct 93 ms 104624 KB Output is correct
26 Incorrect 115 ms 110868 KB Output isn't correct
27 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 103288 KB Output is correct
2 Correct 92 ms 104304 KB Output is correct
3 Correct 107 ms 104568 KB Output is correct
4 Correct 108 ms 104568 KB Output is correct
5 Correct 92 ms 104568 KB Output is correct
6 Correct 91 ms 104568 KB Output is correct
7 Correct 89 ms 104568 KB Output is correct
8 Correct 90 ms 104568 KB Output is correct
9 Correct 115 ms 104568 KB Output is correct
10 Correct 98 ms 104568 KB Output is correct
11 Correct 88 ms 104568 KB Output is correct
12 Correct 120 ms 104568 KB Output is correct
13 Correct 94 ms 104568 KB Output is correct
14 Correct 90 ms 104568 KB Output is correct
15 Correct 105 ms 104568 KB Output is correct
16 Correct 103 ms 104568 KB Output is correct
17 Correct 117 ms 104568 KB Output is correct
18 Correct 88 ms 104568 KB Output is correct
19 Correct 87 ms 104568 KB Output is correct
20 Correct 88 ms 104568 KB Output is correct
21 Correct 92 ms 104568 KB Output is correct
22 Correct 109 ms 104604 KB Output is correct
23 Correct 115 ms 104604 KB Output is correct
24 Correct 109 ms 104604 KB Output is correct
25 Correct 93 ms 104624 KB Output is correct
26 Incorrect 115 ms 110868 KB Output isn't correct
27 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 103288 KB Output is correct
2 Correct 92 ms 104304 KB Output is correct
3 Correct 107 ms 104568 KB Output is correct
4 Correct 108 ms 104568 KB Output is correct
5 Correct 92 ms 104568 KB Output is correct
6 Correct 91 ms 104568 KB Output is correct
7 Correct 89 ms 104568 KB Output is correct
8 Correct 90 ms 104568 KB Output is correct
9 Correct 115 ms 104568 KB Output is correct
10 Correct 98 ms 104568 KB Output is correct
11 Correct 88 ms 104568 KB Output is correct
12 Correct 120 ms 104568 KB Output is correct
13 Correct 94 ms 104568 KB Output is correct
14 Correct 90 ms 104568 KB Output is correct
15 Correct 105 ms 104568 KB Output is correct
16 Correct 103 ms 104568 KB Output is correct
17 Correct 117 ms 104568 KB Output is correct
18 Correct 88 ms 104568 KB Output is correct
19 Correct 87 ms 104568 KB Output is correct
20 Correct 88 ms 104568 KB Output is correct
21 Correct 92 ms 104568 KB Output is correct
22 Correct 109 ms 104604 KB Output is correct
23 Correct 115 ms 104604 KB Output is correct
24 Correct 109 ms 104604 KB Output is correct
25 Correct 93 ms 104624 KB Output is correct
26 Incorrect 115 ms 110868 KB Output isn't correct
27 Halted 0 ms 0 KB -