Submission #563880

#	Time	Username	Problem	Language	Result	Execution time	Memory
563880		tqbfjotld	Wild Boar (JOI18_wild_boar)	C++14	62 / 100	18081 ms	377996 KiB

wild_boar

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1000000000000000000LL;
pair<int,pair<int,int> > edgel[4005];
vector<int> inedge[2005];
vector<int> outedge[2005];

int distm[4005][4005];

pair<int,int> thing1[2005][4005]; //node, edge
pair<int,int> thing2[2005][4005];

int n,m;
int T,L;

int arr[100005];

void handle(int &dist1, int &e1, int &dist2, int &e2, pair<int,int> opt){
    if (e1==opt.second){
        if (opt.first<=dist1){
            dist1 = opt.first;
        }
    }
    else if (e2==opt.second){
        if (opt.first<=dist2){
            dist2 = opt.first;
        }
    }
    else if (opt.first<=dist1){
        dist2 = dist1;
        e2 = e1;
        dist1 = opt.first;
        e1 = opt.second;
    }
    else if (opt.first<=dist2){
        dist2 = opt.first;
        e2 = opt.second;
    }
    if (dist1>dist2){
        swap(dist1,dist2);
        swap(e1,e2);
    }
}

main(){
    scanf("%lld%lld",&n,&m);
    scanf("%lld%lld",&T,&L);
    for (int x = 0; x<m; x++){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        edgel[2*x] = {c,{a,b}};
        edgel[2*x+1] = {c,{b,a}};
        inedge[a].push_back(2*x+1);
        outedge[a].push_back(2*x);
        inedge[b].push_back(2*x);
        outedge[b].push_back(2*x+1);
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    for (int x = 0; x<2*m; x++){
        for (int y = 0; y<2*m; y++){
            distm[x][y] = INF;
        }
        distm[x][x] = 0;
        pq.push({0,x});
        while (!pq.empty()){
            int u = pq.top().second;
            int d = pq.top().first;
            pq.pop();
            if (d>distm[x][u]) continue;
            for (auto y : outedge[edgel[u].second.second]){
                if ((y^1)==u) continue;
                if (d+edgel[y].first<distm[x][y]){
                    distm[x][y] = d+edgel[y].first;
                    pq.push({distm[x][y],y});
                }
            }
        }
    }
    for (int x = 0; x<=2*m; x++){
        for (int y = 1; y<=m; y++){
            thing1[y][x] = {INF,-1};
            thing2[y][x] = {INF,-1};
        }
    }

    for (int x = 0; x<2*m; x++){
        for (int y = 0; y<2*m; y++){
            if (distm[x][y]<INF){
                pair<int,int> nw = {distm[x][y],y};
                if (nw<=thing1[edgel[y].second.second][x]){
                    thing2[edgel[y].second.second][x] = thing1[edgel[y].second.second][x];
                    thing1[edgel[y].second.second][x] = nw;
                }
                else if (nw<=thing2[edgel[y].second.second][x]){
                    thing2[edgel[y].second.second][x] = nw;
                }
            }
        }
    }


    for (int x = 0; x<L; x++){
        scanf("%lld",&arr[x+1]);
    }
    for (int i = 0; i<T; i++){
        int a,b;
        scanf("%lld%lld",&a,&b);
        arr[a] = b;
        int dist1 = INF;
        int e1 = -1;
        int dist2 = INF;
        int e2 = -1;
        for (auto x : outedge[arr[1]]){
            auto t1 = thing1[arr[2]][x];
            t1.first += edgel[x].first;
            if (e1==t1.second){
                if (t1.first<=dist1){
                    dist1 = t1.first;
                }
            }
            else if (e2==t1.second){
                if (t1.first<=dist2){
                    dist2 = t1.first;
                }
            }
            else if (t1.first<=dist1){
                dist2 = dist1;
                e2 = e1;
                dist1 = t1.first;
                e1 = t1.second;
            }
            else if (t1.first<=dist2){
                dist2 = t1.first;
                e2 = t1.second;
            }
            if (dist1>dist2){
                swap(dist1,dist2);
                swap(e1,e2);
            }

            auto t2 = thing2[arr[2]][x];
            t2.first += edgel[x].first;
            if (e1==t2.second){
                if (t2.first<=dist1){
                    dist1 = t2.first;
                }
            }
            else if (e2==t2.second){
                if (t2.first<=dist2){
                    dist2 = t2.first;
                }
            }
            else if (t2.first<=dist1){
                dist2 = dist1;
                e2 = e1;
                dist1 = t2.first;
                e1 = t2.second;
            }
            else if (t2.first<=dist2){
                dist2 = t2.first;
                e2 = t2.second;
            }
            if (dist1>dist2){
                swap(dist1,dist2);
                swap(e1,e2);
            }
        }
        if (dist1==INF){
            printf("-1\n");
            continue;
        }
        for (int x = 3; x<=L; x++){
            //printf("vals are %lld %lld %lld %lld\n",dist1,e1,dist2,e2);

            int ndist1 = INF;
            int ne1 = -1;
            int ndist2 = INF;
            int ne2 = -1;
            auto t1 = thing1[arr[x]][e1];
            t1.first += dist1;
            handle(ndist1,ne1,ndist2,ne2,t1);
            auto t2 = thing2[arr[x]][e1];
            t2.first += dist1;
            handle(ndist1,ne1,ndist2,ne2,t2);
            auto t3 = thing1[arr[x]][e2];
            t3.first += dist2;
            handle(ndist1,ne1,ndist2,ne2,t3);
            auto t4 = thing2[arr[x]][e2];
            t4.first += dist2;
            handle(ndist1,ne1,ndist2,ne2,t4);

            dist1 = ndist1;
            dist2 = ndist2;
            e1 = ne1;
            e2 = ne2;

            if (dist1==INF){
                printf("-1\n");
                break;
            }
        }
        if (dist1==INF) continue;
        printf("%lld\n",dist1);
    }
}

Compilation message (stderr)

wild_boar.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
wild_boar.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%lld%lld",&T,&L);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
wild_boar.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%lld",&arr[x+1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
wild_boar.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%lld%lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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