Submission #133955

#	Time	Username	Problem	Language	Result	Execution time	Memory
133955		duality	Wild Boar (JOI18_wild_boar)	C++11	62 / 100	18134 ms	660432 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;
int num;
vpii adjList[20000];
vi nodes;
int tree[1 << 12];
int build(int s,int e,int i) {
    if (s == e) {
        tree[i] = num++;
        adjList[tree[i]].pb(mp(nodes[s],edges[nodes[s]].w));
        return 0;
    }

    int mid = (s+e) / 2;
    build(s,mid,2*i+1),build(mid+1,e,2*i+2);
    tree[i] = num++;
    adjList[tree[i]].pb(mp(tree[2*i+1],0)),adjList[tree[i]].pb(mp(tree[2*i+2],0));
    return 0;
}
int add(int s,int e,int as,int ae,int i,int u) {
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        adjList[u].pb(mp(tree[i],0));
        return 0;
    }

    int mid = (s+e) / 2;
    add(s,mid,as,ae,2*i+1,u),add(mid+1,e,as,ae,2*i+2,u);
    return 0;
}
priority_queue<pair<LLI,int> > H;
LLI dist2[20000];
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});
    num = edges.size();
    for (i = 0; i <= N; i++) {
        vi v;
        for (j = 0; j < edges.size(); j++) {
            if (edges[j].u == i) nodes.pb(j);
            if (edges[j].v == i) v.pb(j);
        }
        build(0,(int) nodes.size()-1,0);
        for (j = 0; j < v.size(); j++) {
            for (k = 0; k < nodes.size(); k++) {
                if (edges[nodes[k]].v == edges[v[j]].u) break;
            }
            if (k < nodes.size()) {
                add(0,(int) nodes.size()-1,0,k-1,0,v[j]);
                add(0,(int) nodes.size()-1,k+1,(int) nodes.size()-1,0,v[j]);
            }
            else add(0,(int) nodes.size()-1,0,(int) nodes.size()-1,0,v[j]);
        }
        nodes.clear();
    }
    for (i = 0; i < edges.size(); i++) {
        for (j = 0; j < num; j++) dist2[j] = 1e18;
        dist2[i] = 0,H.push(mp(0,i));
        while (!H.empty()) {
            int u = H.top().second;
            LLI d = -H.top().first;
            H.pop();

            if (d > dist2[u]) continue;
            for (j = 0; j < adjList[u].size(); j++) {
                int v = adjList[u][j].first;
                if (d+adjList[u][j].second < dist2[v]) {
                    dist2[v] = d+adjList[u][j].second;
                    H.push(mp(-dist2[v],v));
                }
            }
        }
        for (j = 0; j < edges.size(); j++) dist[i][j] = dist2[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++) {
                if (e1 != -1) b.pb(mp(best[e1][X[j]][k].first+d1,best[e1][X[j]][k].second));
                if (e2 != -1) 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;*/
            }
            while (b.size() < 4) b.pb(mp(1e18,-1));
            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 = min(b[0].first,(LLI) 1e18),ne1 = b[0].second;
            nd2 = min(b[1].first,(LLI) 1e18),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:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < v.size(); j++) {
                     ~~^~~~~~~~~~
wild_boar.cpp:69:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k = 0; k < nodes.size(); k++) {
                         ~~^~~~~~~~~~~~~~
wild_boar.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (k < nodes.size()) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:89:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < adjList[u].size(); j++) {
                         ~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) dist[i][j] = dist2[j];
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:103:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:49: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:51: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:56: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:114: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: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 0 / 38