Submission #133970

#	Time	Username	Problem	Language	Result	Execution time	Memory
133970		duality	Wild Boar (JOI18_wild_boar)	C++11	0 / 100	100 ms	101112 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;

int N,M;
struct edge { int u,v,w; };
vector<edge> edges;
int opp(int a,int b) {
    return ((a < 2*M) && (b < 2*M) && ((a^b) == 1));
}
int X[100000];
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];
struct path { int eu,ev; LLI d; };
bool comp(path a,path b) {
    return a.d < b.d;
}
vector<path> paths[2001][2001];
int shorten(vector<path> &v) {
    if (v.empty()) return 0;
    int i;
    int a,b;
    vector<path> v2;
    sort(v.begin(),v.end(),comp);
    for (i = 1; i < v.size(); i++) {
        if ((v[i].eu == v[0].eu) && (v[i].ev != v[0].ev)) break;
    }
    int p = (i < v.size()) ? i:0;
    v2.pb(v[0]),v2.pb(v[p]);
    for (i = 1; i < v.size(); i++) {
        if (v[i].eu != v[0].eu) break;
    }
    int q = (i < v.size()) ? i:0;
    int m1 = -1,m2 = -1;
    for (i = 1; i < v.size(); i++) {
        if ((i != q) && (v[i].eu == v[q].eu)) {
            if (m1 == -1) m1 = i;
            else if ((m2 == -1) && (v[i].ev != v[m1].ev)) m2 = i;
        }
    }
    if (m1 != -1) v2.pb(v[m1]);
    if (m2 != -1) v2.pb(v[m2]);
    v = v2;
    sort(v.begin(),v.end(),comp);
    return 0;
}
vector<path> com(vector<path> a,vector<path> b) {
    int i,j;
    vector<path> c;
    for (i = 0; i < a.size(); i++) {
        for (j = 0; j < b.size(); j++) {
            if (a[i].ev == b[j].eu) c.pb((path){a[i].eu,b[j].ev,min(a[i].d+b[j].d,(LLI) 1e18)});
        }
    }
    shorten(c);
    return c;
}
vector<path> tree2[1 << 18];
int build2(int s,int e,int i) {
    if (s == e) {
        tree2[i] = paths[X[s-1]][X[s]];
        return 0;
    }

    int mid = (s+e) / 2;
    build2(s,mid,2*i+1),build2(mid+1,e,2*i+2);
    tree2[i] = com(tree2[2*i+1],tree2[2*i+2]);
    return 0;
}
int update2(int s,int e,int ai,int i) {
    if ((s > ai) || (e < ai)) return 0;
    else if (s == e) {
        tree2[i] = paths[X[s-1]][X[s]];
        return 0;
    }

    int mid = (s+e) / 2;
    update2(s,mid,ai,2*i+1),update2(mid+1,e,ai,2*i+2);
    tree2[i] = com(tree2[2*i+1],tree2[2*i+2]);
    return 0;
}
int main() {
    int i;
    int 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 < edges.size(); i++) {
        for (j = 0; j < edges.size(); j++) paths[edges[i].v][edges[j].v].pb((path){i,j,dist[i][j]});
    }
    for (i = 0; i <= N; i++) {
        for (j = 0; j <= N; j++) shorten(paths[i][j]);
    }

    build2(1,L-1,0);
    for (i = 0; i < T; i++) {
        scanf("%d %d",&P,&Q);
        P--,Q--;
        X[P] = Q;
        if (P > 0) update2(1,L-1,P,0);
        if (P < L-1) update2(1,L-1,P+1,0);
        if (tree2[0].empty()) printf("-1\n");
        else printf("%lld\n",(tree2[0][0].d > 1e17) ? -1:tree2[0][0].d);
    }

    return 0;
}

Compilation message (stderr)

wild_boar.cpp: In function 'int shorten(std::vector<path>&)':
wild_boar.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     int p = (i < v.size()) ? i:0;
              ~~^~~~~~~~~~
wild_boar.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     int q = (i < v.size()) ? i:0;
              ~~^~~~~~~~~~
wild_boar.cpp:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:56:9: warning: unused variable 'a' [-Wunused-variable]
     int a,b;
         ^
wild_boar.cpp:56:11: warning: unused variable 'b' [-Wunused-variable]
     int a,b;
           ^
wild_boar.cpp: In function 'std::vector<path> com(std::vector<path>, std::vector<path>)':
wild_boar.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < a.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < b.size(); j++) {
                     ~~^~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:134:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:139:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < v.size(); j++) {
                     ~~^~~~~~~~~~
wild_boar.cpp:140:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k = 0; k < nodes.size(); k++) {
                         ~~^~~~~~~~~~~~~~
wild_boar.cpp:143:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (k < nodes.size()) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:151:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:160:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < adjList[u].size(); j++) {
                         ~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:168: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:170:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:171:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) paths[edges[i].v][edges[j].v].pb((path){i,j,dist[i][j]});
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:120: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:122: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:127: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:179: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: 0 / 12
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38