Submission #133935

#	Time	Username	Problem	Language	Result	Execution time	Memory
133935		duality	Wild Boar (JOI18_wild_boar)	C++11	12 / 100	69 ms	5112 KiB

wild_boar

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

struct edge { int u,v,w; };
vector<edge> edges;
LLI dist[6000][6000];
pair<LLI,int> best[6000][2001][2];
int X[100000];
int main() {
    int i;
    int N,M,T,L;
    int A,B,C,P,Q;
    scanf("%d %d %d %d",&N,&M,&T,&L);
    for (i = 0; i < M; i++) {
        scanf("%d %d %d",&A,&B,&C);
        A--,B--;
        edges.pb((edge){A,B,C});
        edges.pb((edge){B,A,C});
    }
    for (i = 0; i < L; i++) scanf("%d",&X[i]),X[i]--;

    int j,k;
    for (i = 0; i < N; i++) edges.pb((edge){N,i,0});
    for (i = 0; i < edges.size(); i++) fill(dist[i],dist[i]+edges.size(),1e18),dist[i][i] = 0;
    for (i = 0; i < edges.size(); i++) {
        for (j = 0; j < edges.size(); j++) {
            if ((edges[i].v == edges[j].u) && (edges[i].u != edges[j].v)) dist[i][j] = edges[j].w;
        }
    }
    for (k = 0; k < edges.size(); k++) {
        for (i = 0; i < edges.size(); i++) {
            for (j = 0; j < edges.size(); j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
    //for(i=0;i<2*M;i++){
    //    for(j=0;j<2*M;j++)cout<<dist[i][j]<<" ";
    //    cout<<endl;
    //}
    for (i = 0; i < edges.size(); i++) {
        for (j = 0; j < N+1; j++) best[i][j][0] = best[i][j][1] = mp(1e18,-1);
        for (j = 0; j < edges.size(); j++) {
            pair<LLI,int> p = mp(dist[i][j],j);
            if (p.first <= best[i][edges[j].v][0].first)
                best[i][edges[j].v][1] = best[i][edges[j].v][0],best[i][edges[j].v][0] = p;
            else if (p.first <= best[i][edges[j].v][1].first) best[i][edges[j].v][1] = p;
        }
    }

    for (i = 0; i < T; i++) {
        scanf("%d %d",&P,&Q);
        P--,Q--;
        X[P] = Q;
        int u = X[0];
        LLI d1 = 0,d2 = 0;
        int e1 = u+2*M,e2 = u+2*M;
        for (j = 1; j < L; j++) {
            LLI nd1 = 1e18,nd2 = 1e18;
            int ne1 = -1,ne2 = -1;
            vector<pair<LLI,int> > b;
            for (k = 0; k < 2; k++) {
                b.pb(mp(best[e1][X[j]][k].first+d1,best[e1][X[j]][k].second));
                b.pb(mp(best[e2][X[j]][k].first+d2,best[e2][X[j]][k].second));
                /*if ((e1 != -1) && (best[e1][X[j]][k].first+d1 <= nd1))
                    nd2 = nd1,ne2 = ne1,nd1 = best[e1][X[j]][k].first+d1,ne1 = best[e1][X[j]][k].second;
                else if ((e1 != -1) && (best[e1][X[j]][k].first+d1 <= nd2))
                    nd2 = best[e1][X[j]][k].first+d1,ne2 = best[e1][X[j]][k].second;
                if ((e2 != -1) && (best[e2][X[j]][k].first+d2 <= nd1))
                    nd2 = nd1,ne2 = ne1,nd1 = best[e2][X[j]][k].first+d2,ne1 = best[e2][X[j]][k].second;
                else if ((e2 != -1) && (best[e2][X[j]][k].first+d2 <= nd2))
                    nd2 = best[e2][X[j]][k].first+d2,ne2 = best[e2][X[j]][k].second;*/
            }
            sort(b.begin(),b.end());
            if (b[1].second == b[0].second) {
                if (b[2].second == b[0].second) {
                    if (b[3].second != b[0].second) b[1] = b[3];
                }
                else b[1] = b[2];
            }
            nd1 = b[0].first,ne1 = b[0].second;
            nd2 = b[1].first,ne2 = b[1].second;
            d1 = nd1,e1 = ne1,d2 = nd2,e2 = ne2;
        }
        printf("%lld\n",(d1 > 1e17) ? -1:d1);
    }

    return 0;
}

Compilation message (stderr)

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) fill(dist[i],dist[i]+edges.size(),1e18),dist[i][i] = 0;
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (k = 0; k < edges.size(); k++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < edges.size(); i++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:38:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < edges.size(); j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
                         ~~^~~~~~~~~~~~~~
wild_boar.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:19:10: 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:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&A,&B,&C);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:26:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < L; i++) scanf("%d",&X[i]),X[i]--;
                             ~~~~~~~~~~~~~~~~~^~~~~~~
wild_boar.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&P,&Q);
         ~~~~~^~~~~~~~~~~~~~~

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