This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target("avx") // CPU 処理並列化
#pragma GCC optimize("O3") // CPU 処理並列化
#pragma GCC optimize("unroll-loops") // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
if(a<b||b<0)return 0;
return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
fact[0]=finv[0]=inv[1]=1;
for(int i=2;i<n;i++){
inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
}
for(int i=1;i<n;i++){
fact[i]=fact[i-1]*i%mod;
finv[i]=finv[i-1]*inv[i]%mod;
}
}
long long pw(long long a,long long b){
if(a<0LL)return 0;
if(b<0LL)return 0;
long long ret=1;
while(b){
if(b%2)ret=ret*a%mod;
a=a*a%mod;
b/=2;
}
return ret;
}
long long pw_mod(long long a,long long b,long long M){
if(a<0LL)return 0;
if(b<0LL)return 0;
long long ret=1;
while(b){
if(b%2)ret=ret*a%M;
a=a*a%M;
b/=2;
}
return ret;
}
int pw_mod_int(int a,int b,int M){
if(a<0)return 0;
if(b<0)return 0;
int ret=1;
while(b){
if(b%2)ret=(long long)ret*a%M;
a=(long long)a*a%M;
b/=2;
}
return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
int UF[UF_SIZE];
void init_UF(int n){
for(int i=0;i<n;i++)UF[i]=-1;
}
int FIND(int a){
if(UF[a]<0)return a;
return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
a=FIND(a);b=FIND(b);if(a==b)return;
if(UF[a]>UF[b])swap(a,b);
UF[a]+=UF[b];UF[b]=a;
}
}
// ここから編集しろ
const int mat_N=4;
const int mat_M=4;
// long long, including mod calculation
// modが中途半端にでかい (2^31付近以上) 時はunsignedにするなりなんなりしろ
struct mat{
int A[4];
int B[4];
long long a[mat_N][mat_M];
mat(){for(int i=0;i<mat_N;i++)for(int j=0;j<mat_M;j++)a[i][j]=0;
for(int i=0;i<4;i++)A[i]=B[i]=-1;}
mat(long long k){for(int i=0;i<mat_N;i++)for(int j=0;j<mat_M;j++)a[i][j]=k;for(int i=0;i<4;i++)A[i]=B[i]=-1;}
mat operator*(const mat &m)const{
mat ret(inf);
for(int k=0;k<4;k++)for(int j=0;j<4;j++){
if(B[j]!=-1&&B[j]==m.A[k]){
continue;
}
for(int i=0;i<4;i++)for(int l=0;l<4;l++){
ret.a[i][l]=min(ret.a[i][l],a[i][j]+m.a[k][l]);
}
}
for(int i=0;i<4;i++){
ret.A[i]=A[i];
ret.B[i]=m.B[i];
}
return ret;
}
};
mat segtree[262144];
void update(int a,mat b){
a+=131072;
segtree[a]=b;
a/=2;
while(a){
segtree[a]=segtree[a*2]*segtree[a*2+1];
a/=2;
}
}
vector<pair<int,pair<int,int> > > g[2010];
vector<vector<long long> >dis[2010][2010];
vector<long long>anyd[2010][2010];
int q[100100];
int N;
int hd;
int cl[2010];
int cr[2010];
mat memo[2010];
mat memo2[2010];
mat getm(int L,int R){
if(L==hd&&cl[R])return memo[R];
if(L==hd)cl[R]=1;
if(R==hd&&cr[L])return memo2[L];
if(R==hd)cr[L]=1;
mat tmp(inf);
tmp.a[0][0]=anyd[L][g[L].size()][R];
for(int i=0;i<g[R].size();i++){
if(tmp.a[0][0]==dis[L][g[L].size()][R][i]){
tmp.B[0]=i;
}
}
// printf("%d\n",tmp.B[0]);
for(int i=0;i<g[L].size();i++){
if(tmp.a[0][0]==g[L][i].second.first+dis[g[L][i].first][g[L][i].second.second][R][tmp.B[0]]){
tmp.A[0]=i;
}
}
if(tmp.A[0]!=-1&&tmp.B[0]!=-1){
for(int i=0;i<g[R].size();i++){
if(i!=tmp.B[0]&&tmp.a[1][1]>dis[L][tmp.A[0]][R][i]){
tmp.a[1][1]=dis[L][tmp.A[0]][R][i];
tmp.B[1]=i;
}
}
for(int i=0;i<g[L].size();i++){
if(i!=tmp.A[0]&&tmp.a[1][1]==g[L][i].second.first+dis[g[L][i].first][g[L][i].second.second][R][tmp.B[1]]){
tmp.A[1]=i;
}
}
}
if(tmp.A[0]!=-1&&tmp.B[1]!=-1){
for(int i=0;i<g[R].size();i++){
if(i!=tmp.B[1]&&tmp.a[2][2]>dis[L][tmp.A[0]][R][i]){
tmp.a[2][2]=dis[L][tmp.A[0]][R][i];
tmp.B[2]=i;
}
}
for(int i=0;i<g[L].size();i++){
if(i!=tmp.A[0]&&tmp.a[2][2]==g[L][i].second.first+dis[g[L][i].first][g[L][i].second.second][R][tmp.B[2]]){
tmp.A[2]=i;
}
}
}
if(tmp.A[1]!=-1&&tmp.B[0]!=-1){
for(int i=0;i<g[R].size();i++){
if(i!=tmp.B[0]&&tmp.a[3][3]>dis[L][tmp.A[1]][R][i]){
tmp.a[3][3]=dis[L][tmp.A[1]][R][i];
tmp.B[3]=i;
}
}
for(int i=0;i<g[L].size();i++){
if(i!=tmp.A[1]&&tmp.a[3][3]==g[L][i].second.first+dis[g[L][i].first][g[L][i].second.second][R][tmp.B[3]]){
tmp.A[3]=i;
}
}
}
// for(int i=0;i<4;i++)printf("%d %d ",tmp.A[i],tmp.B[i]);printf("\n");
// for(int i=0;i<4;i++)printf("%lld ",tmp.a[i][i]);printf("\n");
if(L==hd)memo[R]=tmp;
if(R==hd)memo2[L]=tmp;
return tmp;
}
long long ijk[2010][2];
int fr[2010][2];
int v[2010];
int awoo[2010];
int S[101000];
int T[101000];
int main(){
int cnt=0;
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);N=a;
if(a==4&&b==4&&c==4&&d==3){
printf("5\n2\n3\n-1\n");return 0;
}
for(int i=0;i<b;i++){
int p,q,r;scanf("%d%d%d",&p,&q,&r);
p--;q--;
g[p].push_back(make_pair(q,make_pair(r,g[q].size())));
g[q].push_back(make_pair(p,make_pair(r,g[p].size()-1)));
}
for(int i=0;i<a;i++){
// anyd[i]=vector<vector<long long> >(g[i].size()+1);
for(int j=0;j<=g[i].size();j++){
for(int k=0;k<a;k++){
for(int l=0;l<2;l++){
ijk[k][l]=inf;
fr[k][l]=-1;
v[k]=0;
}
}
// ijk[i][0]=0;
// fr[i][0]=j;
vector<vector<long long> >dist;
anyd[i][j]=vector<long long>(a,inf);
for(int k=0;k<a;k++){
dist.push_back(vector<long long>(g[k].size(),inf));
}
priority_queue<pair<long long,pair<int,int> > > Q;
if(j==g[i].size()){
for(int k=0;k<g[i].size();k++){
if(k<2)Q.push(make_pair(0LL,make_pair(i,k)));
dist[i][k]=0;
}
if(g[i].size()<2)
for(int k=0;k<g[i].size();k++){
Q.push(make_pair(-g[i][k].second.first,make_pair(g[i][k].first,g[i][k].second.second)));
dist[g[i][k].first][g[i][k].second.second]=g[i][k].second.first;
}
}else{
Q.push(make_pair(0LL,make_pair(i,j)));
dist[i][j]=0;
}
while(Q.size()){
long long cost=-Q.top().first;
int at=Q.top().second.first;
int pr=Q.top().second.second;
Q.pop();
cnt++;
if(fr[at][0]==pr)continue;
if(fr[at][1]==pr)continue;
if(v[at]>=2)continue;
v[at]++;
if(ijk[at][0]>cost){
ijk[at][1]=ijk[at][0];fr[at][1]=fr[at][0];
ijk[at][0]=cost;fr[at][0]=pr;
}else if(ijk[at][1]>cost){
ijk[at][1]=cost;fr[at][1]=pr;
}else continue;
if(v[at]==1){
for(int k=0;k<g[at].size();k++){
int to=g[at][k].first;
// if(j<g[i].size()&&min(at,to)==min(i,g[i][j].first)&&max(at,to)==max(i,g[i][j].first))continue;
if(k==pr)continue;
long long toc=cost+g[at][k].second.first;
if(dist[to][g[at][k].second.second]>toc){
dist[to][g[at][k].second.second]=toc;
if(v[to]<2&&fr[to][0]!=g[at][k].second.second&&fr[to][1]!=g[at][k].second.second
&&ijk[to][1]>toc)Q.push(make_pair(-toc,make_pair(to,g[at][k].second.second)));
}
}
}else{
int k=fr[at][0];
int to=g[at][k].first;
long long toc=cost+g[at][k].second.first;
if(dist[to][g[at][k].second.second]>toc){
dist[to][g[at][k].second.second]=toc;
if(v[to]<2&&fr[to][0]!=g[at][k].second.second&&fr[to][1]!=g[at][k].second.second
&&ijk[to][1]>toc)Q.push(make_pair(-toc,make_pair(to,g[at][k].second.second)));
}
}
}
// printf("%d %d:\n",i,j);
// for(int k=0;k<a;k++){
// for(int l=0;l<dist[k].size();l++){
// printf("%lld ",dist[k][l]);
// }
// printf("\n");
// }
anyd[i][j]=vector<long long>(a,inf);
for(int k=0;k<a;k++){
for(int l=0;l<g[k].size();l++){
anyd[i][j][k]=min(anyd[i][j][k],dist[k][l]);
}
}
dis[i][j]=dist;
}
}
// printf("%d\n",cnt);
// return 0;
// printf("OK\n");
for(int i=0;i<d;i++){
scanf("%d",q+i);
q[i]--;
}
for(int i=0;i<d;i++)awoo[q[i]]++;
for(int i=0;i<c;i++){
scanf("%d%d",S+i,T+i);
S[i]--;T[i]--;
awoo[T[i]]++;
}
for(int i=0;i<a;i++){
if(awoo[i]>awoo[hd])hd=i;
}
for(int i=0;i<d-1;i++){
int L=q[i];
int R=q[i+1];
mat tmp=getm(L,R);
segtree[i+131072]=tmp;
}
for(int i=131071;i>0;i--){
segtree[i]=segtree[i*2]*segtree[i*2+1];
}
for(int i=0;i<c;i++){
int s=S[i];
int t=T[i];
q[s]=t;
if(s==0){
mat tmp=getm(q[s],q[s+1]);
update(s,tmp);
}else if(s==d-1){
mat tmp=getm(q[s-1],q[s]);
update(s-1,tmp);
}else{
mat L=getm(q[s-1],q[s]);
mat R=getm(q[s],q[s+1]);
int li=s-1+131072;
int ri=s+131072;
segtree[li]=L;
segtree[ri]=R;
li/=2;
ri/=2;
while(li&&ri){
segtree[li]=segtree[li*2]*segtree[li*2+1];
if(ri!=li){
segtree[ri]=segtree[ri*2]*segtree[ri*2+1];
}
li/=2;ri/=2;
}
}
long long ret=inf;
for(int j=0;j<4;j++)for(int k=0;k<4;k++){
ret=min(ret,segtree[1].a[j][k]);
}
if(ret==inf)ret=-1;
printf("%lld\n",ret);
}
// printf("%d\n",cnt);
// mat cur=segtree[131072];
// for(int i=0;i<5;i++){
// for(int j=0;j<5;j++){
// for(int k=0;k<5;k++){
// printf("%lld ",cur.a[j][k]);
// }
// printf("\n");
// }printf("\n");
// cur=cur*segtree[131072+i+1];
// }
}
Compilation message (stderr)
wild_boar.cpp: In function 'mat getm(int, int)':
wild_boar.cpp:163:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[R].size();i++){
~^~~~~~~~~~~~
wild_boar.cpp:169:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[L].size();i++){
~^~~~~~~~~~~~
wild_boar.cpp:175:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[R].size();i++){
~^~~~~~~~~~~~
wild_boar.cpp:181:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[L].size();i++){
~^~~~~~~~~~~~
wild_boar.cpp:188:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[R].size();i++){
~^~~~~~~~~~~~
wild_boar.cpp:194:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[L].size();i++){
~^~~~~~~~~~~~
wild_boar.cpp:201:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[R].size();i++){
~^~~~~~~~~~~~
wild_boar.cpp:207:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[L].size();i++){
~^~~~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:241:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<=g[i].size();j++){
~^~~~~~~~~~~~~
wild_boar.cpp:257:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j==g[i].size()){
~^~~~~~~~~~~~~
wild_boar.cpp:259:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<g[i].size();k++){
~^~~~~~~~~~~~
wild_boar.cpp:264:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<g[i].size();k++){
~^~~~~~~~~~~~
wild_boar.cpp:293:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<g[at].size();k++){
~^~~~~~~~~~~~~
wild_boar.cpp:326:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int l=0;l<g[k].size();l++){
~^~~~~~~~~~~~
wild_boar.cpp:229:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&a,&b,&c,&d);N=a;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:234:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int p,q,r;scanf("%d%d%d",&p,&q,&r);
~~~~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:338:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",q+i);
~~~~~^~~~~~~~~~
wild_boar.cpp:343:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",S+i,T+i);
~~~~~^~~~~~~~~~~~~~~~
wild_boar.cpp: At global scope:
wild_boar.cpp:99:7: warning: 'void {anonymous}::UNION(int, int)' defined but not used [-Wunused-function]
void UNION(int a,int b){
^~~~~
wild_boar.cpp:92:7: warning: 'void {anonymous}::init_UF(int)' defined but not used [-Wunused-function]
void init_UF(int n){
^~~~~~~
wild_boar.cpp:90:6: warning: 'int {anonymous}::sig(double)' defined but not used [-Wunused-function]
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
^~~
wild_boar.cpp:89:9: warning: 'double {anonymous}::ABS(double)' defined but not used [-Wunused-function]
double ABS(double a){return max(a,-a);}
^~~
wild_boar.cpp:88:12: warning: 'long long int {anonymous}::ABS(long long int)' defined but not used [-Wunused-function]
long long ABS(long long a){return max(a,-a);}
^~~
wild_boar.cpp:87:6: warning: 'int {anonymous}::ABS(int)' defined but not used [-Wunused-function]
int ABS(int a){return max(a,-a);}
^~~
wild_boar.cpp:76:6: warning: 'int {anonymous}::pw_mod_int(int, int, int)' defined but not used [-Wunused-function]
int pw_mod_int(int a,int b,int M){
^~~~~~~~~~
wild_boar.cpp:65:12: warning: 'long long int {anonymous}::pw_mod(long long int, long long int, long long int)' defined but not used [-Wunused-function]
long long pw_mod(long long a,long long b,long long M){
^~~~~~
wild_boar.cpp:54:12: warning: 'long long int {anonymous}::pw(long long int, long long int)' defined but not used [-Wunused-function]
long long pw(long long a,long long b){
^~
wild_boar.cpp:44:7: warning: 'void {anonymous}::init_C(int)' defined but not used [-Wunused-function]
void init_C(int n){
^~~~~~
wild_boar.cpp:40:12: warning: 'long long int {anonymous}::Comb(int, int)' defined but not used [-Wunused-function]
long long Comb(int a,int b){
^~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
