제출 #69650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69650		yogahmad	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	10572 ms	11036 KiB

wild_boar

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 4003
#define pc(x) putchar_unlocked(x);
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;

long long n,u,v,w,m,t,l,di[mx][mx],x[100003];
pair<long long,int>dist1[mx][mx],dist2[mx][mx],ini[mx],bisa1[mx][mx],bisa2[mx][mx];
struct edge{
	long long v,w,id;
};

vector<edge>g[mx];

void apsp(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			bisa1[i][j]={-1,0};
			bisa2[i][j]={-1,0};
		}
	}
	for(int dari=1;dari<=n;dari++){
		priority_queue<pair<long long,pair<int,int>>>q;
		bisa1[dari][dari]={0,0};
		q.push({0,{dari,0}});
		while(!q.empty()){
			auto now=q.top().s;
			auto sem=q.top().f;
			q.pop();
			for(auto i:g[now.f]){
				if(i.v==now.s)continue;
				auto nxt=-sem+i.w;
				if(bisa1[dari][i.v].f==-1 || bisa1[dari][i.v].f>nxt){
					assert(bisa1[dari][i.v].s!=now.f);
					bisa2[dari][i.v]=bisa1[dari][i.v];
					bisa1[dari][i.v]={nxt,now.f};
					q.push({-nxt,{i.v,now.f}});
				}
				else if((bisa2[dari][i.v].f==-1 || bisa2[dari][i.v].f>nxt) && now.f!=bisa1[dari][i.v].s){
					bisa2[dari][i.v]={nxt,now.f};
					q.push({-nxt,{i.v,now.f}});
				}
			}
		}
	}
}

void comp(int cnt){
	for(int i=1;i<=n;i++){
		dist1[cnt][i]={-1,0};
		dist2[cnt][i]={-1,0};
	}
	priority_queue<pair<long long,pair<int,int>>>q;
	for(auto i:g[ini[cnt].f]){
		if(i.v==ini[cnt].s)continue;
		dist1[cnt][i.v].f=i.w;
		dist1[cnt][i.v].s=ini[cnt].f;
		q.push({-i.w,{i.v,ini[cnt].f}});
	}
	while(!q.empty()){
		auto now=q.top().s;
		auto sem=q.top().f;
		q.pop();
		for(auto i:g[now.f]){
			if(i.v==now.s)continue;
			auto nxt=-sem+i.w;
			if(dist1[cnt][i.v].f==-1 || dist1[cnt][i.v].f>nxt){
				assert(dist1[cnt][i.v].s!=now.f);
				dist2[cnt][i.v]=dist1[cnt][i.v];
				dist1[cnt][i.v]={nxt,now.f};
				q.push({-nxt,{i.v,now.f}});
			}
			else if((dist2[cnt][i.v].f==-1 || dist2[cnt][i.v].f>nxt) && now.f!=dist1[cnt][i.v].s){
				dist2[cnt][i.v]={nxt,now.f};
				q.push({-nxt,{i.v,now.f}});
			}
		}
	}
}

long long hitung(){
	auto sa=bisa1[x[1]][x[2]];
	auto du=bisa2[x[1]][x[2]];
	vector<pair<long long,int>>ve,sem;
	if(sa.f!=-1)ve.pb(sa);
	if(du.f!=-1)ve.pb(du);
	for(int i=2;i<l;i++){
		sem.clear();
		for(auto xx:ve){
			int idx=di[x[i]][xx.s];
			auto a=dist1[idx][x[i+1]];
			if(a.f!=-1){
				a.f+=xx.f;
				sem.pb(a);
			}
			auto b=dist2[idx][x[i+1]];
			if(b.f!=-1){
				b.f+=xx.f;
				sem.pb(b);
			}
		}
		ve=sem;
		sort(ALL(ve));
		ve.erase((unique(ALL(ve))),ve.end());
		while(ve.size()>1000)ve.pop_back();
	}
	long long mini=-1;
	for(auto i:ve){
		assert(i.f!=-1);
		if(mini==-1 || mini>i.f)mini=i.f;
	}
	return mini;
}

int main(){
	scanf("%d%d%d%d",&n,&m,&t,&l);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		g[u].pb({v,w,i});
		g[v].pb({u,w,i});
	}
	int cnt=0;
	apsp();
	for(int i=1;i<=n;i++){
		for(auto j:g[i]){
			di[i][j.v]=cnt;
			ini[cnt]={i,j.v};
			comp(cnt);
			cnt++;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
	//		cout<<i<<" - satu > "<<j<<' '<<bisa1[i][j].f<<" "<<bisa1[i][j].s<<endl;
	//		cout<<i<<" - dua  > "<<j<<' '<<bisa2[i][j].f<<" "<<bisa2[i][j].s<<endl;
		}
	}
	for(int i=1;i<=l;i++)cin>>x[i];
	for(int i=0;i<cnt;i++){
		for(int j=1;j<=n;j++){
			if(dist1[i][j].f!=-1 && dist2[i][j].f!=-1){
				//cout<<i<<' '<<j<<endl;
				assert(dist1[i][j].s!=dist2[i][j].s);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(bisa1[i][j].f!=-1 && bisa2[i][j].f!=-1){
				assert(bisa1[i][j].s!=bisa2[i][j].s);
			}
		}
	}
	while(t--){
		int l,r;
		scanf("%d%d",&l,&r);
		x[l]=r;
		printf("%lld\n",hitung());
	}
}

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

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:129:30: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d%d%d%d",&n,&m,&t,&l);
                   ~~         ^
wild_boar.cpp:129:30: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
wild_boar.cpp:129:30: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
wild_boar.cpp:129:30: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
wild_boar.cpp:131:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d%d%d",&u,&v,&w);
                  ~~      ^
wild_boar.cpp:131:26: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
wild_boar.cpp:131:26: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
wild_boar.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&n,&m,&t,&l);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:131: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&l,&r);
   ~~~~~^~~~~~~~~~~~~~

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