Submission #58287

#	Time	Username	Problem	Language	Result	Execution time	Memory
58287		sebinkim	Wild Boar (JOI18_wild_boar)	C++14	0 / 100	109 ms	103552 KiB

wild_boar

#include <bits/stdc++.h>

using namespace std;

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

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];
ll chk[2020][2];
ll L[101010];
ll n, m, k;

vp add(vp &a, vp &b)
{
	vp ret, ans;
	ll i, j, c1, c2;
	
	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());
		
		ans.push_back(ret[0]);
		
		for(i=1;i<ret.size();i++){
			if(ret[i].s != ret[0].s && ret[i].e != ret[0].e) break;
		}
		
		if(i < ret.size()){
			ans.push_back(ret[i]);
			
			ll s1 = ret[0].s, e1 = ret[i].e;
			ll s2 = ret[i].s, e2 = ret[0].e;
			ll a;
			
			for(a=1;a<ret.size();a++) if(ret[a].s != s1 && ret[a].e != e1) break;
			if(a < ret.size()) ans.push_back(ret[a]);
			
			for(a=1;a<ret.size();a++) if(ret[a].s != s2 && ret[a].e != e2) break;
			if(a < ret.size()) ans.push_back(ret[a]);
		}
		else{
			ll a;
			ll s = ret[0].s, e = ret[0].e;
			
			for(a=1;a<ret.size();a++) if(ret[a].s != s) break;
			if(a < ret.size()) ans.push_back(ret[a]);
			
			for(a=1;a<ret.size();a++) if(ret[a].e != e) break;
			if(a < ret.size()) ans.push_back(ret[a]);
		}
	}
	
	return ans;
}

void dijkstra(ll a, ll b, ll v)
{
	path p;
	ll i;
	
	chk[a][0] = 1;
	
	Q.push(path(v, a, b));
	
	for(;!Q.empty();){
		p = Q.top(); Q.pop();
		
		if(chk[p.e][0] && chk[p.e][1]) continue;
		if(p.s == chk[p.e][0] || p.e == chk[p.e][1]) continue;
		
		if(chk[p.e][0]) chk[p.e][1] = p.s;
		else chk[p.e][0] = p.s;
		
		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++){
		chk[i][0] = chk[i][1] = 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()){
			vp ret = K[i][j], ans;
			ll a;
			
			sort(ret.begin(), ret.end());
			reverse(ret.begin(), ret.end());
			
			ans.push_back(ret[0]);
			
			for(a=1;a<ret.size();a++){
				if(ret[a].s != ret[0].s && ret[a].e != ret[0].e) break;
			}
			
			if(a < ret.size()){
				ans.push_back(ret[a]);
				
				ll s1 = ret[0].s, e1 = ret[a].e;
				ll s2 = ret[a].s, e2 = ret[0].e;
				
				for(a=1;a<ret.size();a++) if(ret[a].s != s1 && ret[a].e != e1) break;
				if(a < ret.size()) ans.push_back(ret[a]);
				
				for(a=1;a<ret.size();a++) if(ret[a].s != s2 && ret[a].e != e2) break;
				if(a < ret.size()) ans.push_back(ret[a]);
			}
			else{
				ll s = ret[0].s, e = ret[0].e;
				
				for(a=1;a<ret.size();a++) if(ret[a].s != s) break;
				if(a < ret.size()) ans.push_back(ret[a]);
				
				for(a=1;a<ret.size();a++) if(ret[a].e != e) break;
				if(a < ret.size()) ans.push_back(ret[a]);
			}
			
			K[i][j] = ans;
		}
	}
	
	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 (stderr)

wild_boar.cpp: In function 'vp add(vp&, vp&)':
wild_boar.cpp:44:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=1;i<ret.size();i++){
           ~^~~~~~~~~~~
wild_boar.cpp:48:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i < ret.size()){
      ~~^~~~~~~~~~~~
wild_boar.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(a=1;a<ret.size();a++) if(ret[a].s != s1 && ret[a].e != e1) break;
            ~^~~~~~~~~~~
wild_boar.cpp:56:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(a < ret.size()) ans.push_back(ret[a]);
       ~~^~~~~~~~~~~~
wild_boar.cpp:58:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(a=1;a<ret.size();a++) if(ret[a].s != s2 && ret[a].e != e2) break;
            ~^~~~~~~~~~~
wild_boar.cpp:59:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(a < ret.size()) ans.push_back(ret[a]);
       ~~^~~~~~~~~~~~
wild_boar.cpp:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(a=1;a<ret.size();a++) if(ret[a].s != s) break;
            ~^~~~~~~~~~~
wild_boar.cpp:66:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(a < ret.size()) ans.push_back(ret[a]);
       ~~^~~~~~~~~~~~
wild_boar.cpp:68:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(a=1;a<ret.size();a++) if(ret[a].e != e) break;
            ~^~~~~~~~~~~
wild_boar.cpp:69:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(a < ret.size()) ans.push_back(ret[a]);
       ~~^~~~~~~~~~~~
wild_boar.cpp:28:8: warning: unused variable 'j' [-Wunused-variable]
  ll i, j, c1, c2;
        ^
wild_boar.cpp:28:11: warning: unused variable 'c1' [-Wunused-variable]
  ll i, j, c1, c2;
           ^~
wild_boar.cpp:28:15: warning: unused variable 'c2' [-Wunused-variable]
  ll i, j, c1, c2;
               ^~
wild_boar.cpp: In function 'void init_seg(ll, ll, ll)':
wild_boar.cpp:115:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  init_seg(p<<1, s, (s+e>>1));
                     ~^~
wild_boar.cpp:116: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:128:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= (s+e>>1)) update(p<<1, s, (s+e>>1), v);
           ~^~
wild_boar.cpp:128:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= (s+e>>1)) update(p<<1, s, (s+e>>1), v);
                                     ~^~
wild_boar.cpp:129: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:161:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(a=1;a<ret.size();a++){
            ~^~~~~~~~~~~
wild_boar.cpp:165:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(a < ret.size()){
       ~~^~~~~~~~~~~~
wild_boar.cpp:171:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(a=1;a<ret.size();a++) if(ret[a].s != s1 && ret[a].e != e1) break;
             ~^~~~~~~~~~~
wild_boar.cpp:172:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a < ret.size()) ans.push_back(ret[a]);
        ~~^~~~~~~~~~~~
wild_boar.cpp:174:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(a=1;a<ret.size();a++) if(ret[a].s != s2 && ret[a].e != e2) break;
             ~^~~~~~~~~~~
wild_boar.cpp:175:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a < ret.size()) ans.push_back(ret[a]);
        ~~^~~~~~~~~~~~
wild_boar.cpp:180:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(a=1;a<ret.size();a++) if(ret[a].s != s) break;
             ~^~~~~~~~~~~
wild_boar.cpp:181:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a < ret.size()) ans.push_back(ret[a]);
        ~~^~~~~~~~~~~~
wild_boar.cpp:183:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(a=1;a<ret.size();a++) if(ret[a].e != e) break;
             ~^~~~~~~~~~~
wild_boar.cpp:184:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a < ret.size()) ans.push_back(ret[a]);
        ~~^~~~~~~~~~~~
wild_boar.cpp:139: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:142: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:192: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:198:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38