oj.uz

Submission #133982

# Submission time Handle Problem Language Result Execution time Memory
133982 2019-07-21T20:38:34 Z duality Wild Boar (JOI18_wild_boar) C++11
100 / 100
 15832 ms 653060 KB 
#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) return 0;

    int mid = (s+e) / 2;
    build(s,mid,2*i+1),build(mid+1,e,2*i+2);
    tree[i] = num++;
    if (s == mid) adjList[tree[i]].pb(mp(nodes[s],edges[nodes[s]].w));
    else adjList[tree[i]].pb(mp(tree[2*i+1],0));
    if (mid+1 == e) adjList[tree[i]].pb(mp(nodes[e],edges[nodes[e]].w));
    else 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)) {
        if (s == e) adjList[u].pb(mp(nodes[s],edges[nodes[s]].w));
        else 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[4000][4000];
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) {
    int i;
    vector<path> v2;
    sort(v.begin(),v.end(),comp);
    while (!v.empty() && (v.back().d > 1e17)) v.pop_back();
    if (v.empty()) return 0;
    v2.pb(v[0]);
    for (i = 1; i < v.size(); i++) {
        if ((v[i].eu != v[0].eu) && (v[i].ev != v[0].ev)) {
            v2.pb(v[i]);
            break;
        }
    }
    int m1 = -1,m2 = -1;
    for (i = 1; i < v.size(); i++) {
        if (v[i].eu != v[0].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]),m1 = -1;
    if (m2 != -1) v2.pb(v[m2]),m2 = -1;
    for (i = 1; i < v.size(); i++) {
        if (v[i].ev != v[0].ev) {
            if (m1 == -1) m1 = i;
            else if ((m2 == -1) && (v[i].eu != v[m1].eu)) m2 = i;
        }
    }
    if (m1 != -1) v2.pb(v[m1]),m1 = -1;
    if (m2 != -1) v2.pb(v[m2]),m2 = -1;
    v.clear(),v = v2;
    sort(v.begin(),v.end(),comp);
    v.shrink_to_fit();
    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 (!opp(a[i].ev,b[j].eu)) c.pb((path){a[i].eu,b[j].ev,a[i].d+b[j].d});
        }
    }
    shorten(c);
    return c;
}
vector<path> tree2[1 << 18];
int build2(int s,int e,int i) {
    if (s == e) {
        tree2[i] = paths[(s == 0) ? N: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].clear();
        tree2[i] = paths[(s == 0) ? N: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;
    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 < num; i++) adjList[i].clear(),adjList[i].shrink_to_fit();
    for (i = 0; i < edges.size(); i++) {
        for (j = 0; j < edges.size(); j++) {
            if ((edges[i].u != edges[j].v) && (dist[i][j] < 1e18))
                paths[edges[i].u][edges[j].v].pb((path){i,j,dist[i][j]+edges[i].w});
        }
    }
    for (i = 0; i < N; i++) paths[N][i].pb((path){2*M+i,2*M+i,0});
    for (i = 0; i <= N; i++) {
        for (j = 0; j <= N; j++) shorten(paths[i][j]);
    }

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

    return 0;
}

Compilation message

wild_boar.cpp: In function 'int shorten(std::vector<path>&)':
wild_boar.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp: In function 'std::vector<path> com(std::vector<path>, std::vector<path>)':
wild_boar.cpp:91:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < a.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:92: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:141:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:146:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < v.size(); j++) {
                     ~~^~~~~~~~~~
wild_boar.cpp:147:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k = 0; k < nodes.size(); k++) {
                         ~~^~~~~~~~~~~~~~
wild_boar.cpp:150:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (k < nodes.size()) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:167:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < adjList[u].size(); j++) {
                         ~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:175: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:178:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:179:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:128: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:130: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:135: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:191: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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 101056 KB Output is correct
2 Correct 96 ms 101112 KB Output is correct
3 Correct 101 ms 101240 KB Output is correct
4 Correct 95 ms 101112 KB Output is correct
5 Correct 95 ms 101112 KB Output is correct
6 Correct 94 ms 101088 KB Output is correct
7 Correct 94 ms 101112 KB Output is correct
8 Correct 94 ms 101084 KB Output is correct
9 Correct 94 ms 101112 KB Output is correct
10 Correct 95 ms 101112 KB Output is correct
11 Correct 96 ms 101272 KB Output is correct
12 Correct 95 ms 101112 KB Output is correct
13 Correct 95 ms 101112 KB Output is correct
14 Correct 94 ms 101112 KB Output is correct
15 Correct 96 ms 101120 KB Output is correct
16 Correct 96 ms 101180 KB Output is correct
17 Correct 95 ms 101092 KB Output is correct
18 Correct 95 ms 101112 KB Output is correct
19 Correct 95 ms 101112 KB Output is correct
20 Correct 95 ms 101120 KB Output is correct
21 Correct 93 ms 101020 KB Output is correct
22 Correct 95 ms 101112 KB Output is correct
23 Correct 94 ms 101092 KB Output is correct
24 Correct 94 ms 101116 KB Output is correct
25 Correct 95 ms 101048 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 101056 KB Output is correct
2 Correct 96 ms 101112 KB Output is correct
3 Correct 101 ms 101240 KB Output is correct
4 Correct 95 ms 101112 KB Output is correct
5 Correct 95 ms 101112 KB Output is correct
6 Correct 94 ms 101088 KB Output is correct
7 Correct 94 ms 101112 KB Output is correct
8 Correct 94 ms 101084 KB Output is correct
9 Correct 94 ms 101112 KB Output is correct
10 Correct 95 ms 101112 KB Output is correct
11 Correct 96 ms 101272 KB Output is correct
12 Correct 95 ms 101112 KB Output is correct
13 Correct 95 ms 101112 KB Output is correct
14 Correct 94 ms 101112 KB Output is correct
15 Correct 96 ms 101120 KB Output is correct
16 Correct 96 ms 101180 KB Output is correct
17 Correct 95 ms 101092 KB Output is correct
18 Correct 95 ms 101112 KB Output is correct
19 Correct 95 ms 101112 KB Output is correct
20 Correct 95 ms 101120 KB Output is correct
21 Correct 93 ms 101020 KB Output is correct
22 Correct 95 ms 101112 KB Output is correct
23 Correct 94 ms 101092 KB Output is correct
24 Correct 94 ms 101116 KB Output is correct
25 Correct 95 ms 101048 KB Output is correct
26 Correct 100 ms 101676 KB Output is correct
27 Correct 138 ms 107128 KB Output is correct
28 Correct 133 ms 106488 KB Output is correct
29 Correct 534 ms 132212 KB Output is correct
30 Correct 583 ms 132088 KB Output is correct
31 Correct 538 ms 132120 KB Output is correct
32 Correct 484 ms 131836 KB Output is correct
33 Correct 529 ms 133928 KB Output is correct
34 Correct 562 ms 133964 KB Output is correct
35 Correct 502 ms 133560 KB Output is correct
36 Correct 557 ms 133496 KB Output is correct
37 Correct 578 ms 133880 KB Output is correct
38 Correct 500 ms 136328 KB Output is correct
39 Correct 513 ms 135672 KB Output is correct
40 Correct 543 ms 136312 KB Output is correct
41 Correct 574 ms 136312 KB Output is correct
42 Correct 440 ms 137080 KB Output is correct
43 Correct 480 ms 139000 KB Output is correct
44 Correct 503 ms 139000 KB Output is correct
45 Correct 303 ms 131960 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 101056 KB Output is correct
2 Correct 96 ms 101112 KB Output is correct
3 Correct 101 ms 101240 KB Output is correct
4 Correct 95 ms 101112 KB Output is correct
5 Correct 95 ms 101112 KB Output is correct
6 Correct 94 ms 101088 KB Output is correct
7 Correct 94 ms 101112 KB Output is correct
8 Correct 94 ms 101084 KB Output is correct
9 Correct 94 ms 101112 KB Output is correct
10 Correct 95 ms 101112 KB Output is correct
11 Correct 96 ms 101272 KB Output is correct
12 Correct 95 ms 101112 KB Output is correct
13 Correct 95 ms 101112 KB Output is correct
14 Correct 94 ms 101112 KB Output is correct
15 Correct 96 ms 101120 KB Output is correct
16 Correct 96 ms 101180 KB Output is correct
17 Correct 95 ms 101092 KB Output is correct
18 Correct 95 ms 101112 KB Output is correct
19 Correct 95 ms 101112 KB Output is correct
20 Correct 95 ms 101120 KB Output is correct
21 Correct 93 ms 101020 KB Output is correct
22 Correct 95 ms 101112 KB Output is correct
23 Correct 94 ms 101092 KB Output is correct
24 Correct 94 ms 101116 KB Output is correct
25 Correct 95 ms 101048 KB Output is correct
26 Correct 100 ms 101676 KB Output is correct
27 Correct 138 ms 107128 KB Output is correct
28 Correct 133 ms 106488 KB Output is correct
29 Correct 534 ms 132212 KB Output is correct
30 Correct 583 ms 132088 KB Output is correct
31 Correct 538 ms 132120 KB Output is correct
32 Correct 484 ms 131836 KB Output is correct
33 Correct 529 ms 133928 KB Output is correct
34 Correct 562 ms 133964 KB Output is correct
35 Correct 502 ms 133560 KB Output is correct
36 Correct 557 ms 133496 KB Output is correct
37 Correct 578 ms 133880 KB Output is correct
38 Correct 500 ms 136328 KB Output is correct
39 Correct 513 ms 135672 KB Output is correct
40 Correct 543 ms 136312 KB Output is correct
41 Correct 574 ms 136312 KB Output is correct
42 Correct 440 ms 137080 KB Output is correct
43 Correct 480 ms 139000 KB Output is correct
44 Correct 503 ms 139000 KB Output is correct
45 Correct 303 ms 131960 KB Output is correct
46 Correct 480 ms 135388 KB Output is correct
47 Correct 7553 ms 547144 KB Output is correct
48 Correct 7154 ms 547364 KB Output is correct
49 Correct 7332 ms 575636 KB Output is correct
50 Correct 7143 ms 563312 KB Output is correct
51 Correct 7126 ms 560956 KB Output is correct
52 Correct 7311 ms 592376 KB Output is correct
53 Correct 7165 ms 595140 KB Output is correct
54 Correct 7122 ms 590580 KB Output is correct
55 Correct 7319 ms 593604 KB Output is correct
56 Correct 7091 ms 596024 KB Output is correct
57 Correct 7090 ms 595524 KB Output is correct
58 Correct 7022 ms 596956 KB Output is correct
59 Correct 7005 ms 601392 KB Output is correct
60 Correct 6965 ms 598352 KB Output is correct
61 Correct 6925 ms 597804 KB Output is correct
62 Correct 6754 ms 607936 KB Output is correct
63 Correct 6418 ms 650496 KB Output is correct
64 Correct 3172 ms 582520 KB Output is correct
65 Correct 3101 ms 582648 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 101056 KB Output is correct
2 Correct 96 ms 101112 KB Output is correct
3 Correct 101 ms 101240 KB Output is correct
4 Correct 95 ms 101112 KB Output is correct
5 Correct 95 ms 101112 KB Output is correct
6 Correct 94 ms 101088 KB Output is correct
7 Correct 94 ms 101112 KB Output is correct
8 Correct 94 ms 101084 KB Output is correct
9 Correct 94 ms 101112 KB Output is correct
10 Correct 95 ms 101112 KB Output is correct
11 Correct 96 ms 101272 KB Output is correct
12 Correct 95 ms 101112 KB Output is correct
13 Correct 95 ms 101112 KB Output is correct
14 Correct 94 ms 101112 KB Output is correct
15 Correct 96 ms 101120 KB Output is correct
16 Correct 96 ms 101180 KB Output is correct
17 Correct 95 ms 101092 KB Output is correct
18 Correct 95 ms 101112 KB Output is correct
19 Correct 95 ms 101112 KB Output is correct
20 Correct 95 ms 101120 KB Output is correct
21 Correct 93 ms 101020 KB Output is correct
22 Correct 95 ms 101112 KB Output is correct
23 Correct 94 ms 101092 KB Output is correct
24 Correct 94 ms 101116 KB Output is correct
25 Correct 95 ms 101048 KB Output is correct
26 Correct 100 ms 101676 KB Output is correct
27 Correct 138 ms 107128 KB Output is correct
28 Correct 133 ms 106488 KB Output is correct
29 Correct 534 ms 132212 KB Output is correct
30 Correct 583 ms 132088 KB Output is correct
31 Correct 538 ms 132120 KB Output is correct
32 Correct 484 ms 131836 KB Output is correct
33 Correct 529 ms 133928 KB Output is correct
34 Correct 562 ms 133964 KB Output is correct
35 Correct 502 ms 133560 KB Output is correct
36 Correct 557 ms 133496 KB Output is correct
37 Correct 578 ms 133880 KB Output is correct
38 Correct 500 ms 136328 KB Output is correct
39 Correct 513 ms 135672 KB Output is correct
40 Correct 543 ms 136312 KB Output is correct
41 Correct 574 ms 136312 KB Output is correct
42 Correct 440 ms 137080 KB Output is correct
43 Correct 480 ms 139000 KB Output is correct
44 Correct 503 ms 139000 KB Output is correct
45 Correct 303 ms 131960 KB Output is correct
46 Correct 480 ms 135388 KB Output is correct
47 Correct 7553 ms 547144 KB Output is correct
48 Correct 7154 ms 547364 KB Output is correct
49 Correct 7332 ms 575636 KB Output is correct
50 Correct 7143 ms 563312 KB Output is correct
51 Correct 7126 ms 560956 KB Output is correct
52 Correct 7311 ms 592376 KB Output is correct
53 Correct 7165 ms 595140 KB Output is correct
54 Correct 7122 ms 590580 KB Output is correct
55 Correct 7319 ms 593604 KB Output is correct
56 Correct 7091 ms 596024 KB Output is correct
57 Correct 7090 ms 595524 KB Output is correct
58 Correct 7022 ms 596956 KB Output is correct
59 Correct 7005 ms 601392 KB Output is correct
60 Correct 6965 ms 598352 KB Output is correct
61 Correct 6925 ms 597804 KB Output is correct
62 Correct 6754 ms 607936 KB Output is correct
63 Correct 6418 ms 650496 KB Output is correct
64 Correct 3172 ms 582520 KB Output is correct
65 Correct 3101 ms 582648 KB Output is correct
66 Correct 407 ms 126712 KB Output is correct
67 Correct 619 ms 173820 KB Output is correct
68 Correct 1609 ms 355064 KB Output is correct
69 Correct 1796 ms 357820 KB Output is correct
70 Correct 1971 ms 361720 KB Output is correct
71 Correct 15582 ms 541904 KB Output is correct
72 Correct 15832 ms 555312 KB Output is correct
73 Correct 14230 ms 594608 KB Output is correct
74 Correct 14251 ms 597192 KB Output is correct
75 Correct 14274 ms 595616 KB Output is correct
76 Correct 15387 ms 573532 KB Output is correct
77 Correct 15717 ms 562052 KB Output is correct
78 Correct 11835 ms 556564 KB Output is correct
79 Correct 13792 ms 601452 KB Output is correct
80 Correct 13625 ms 601996 KB Output is correct
81 Correct 14059 ms 588928 KB Output is correct
82 Correct 12983 ms 603748 KB Output is correct
83 Correct 15109 ms 600840 KB Output is correct
84 Correct 11921 ms 653060 KB Output is correct
85 Correct 6442 ms 585320 KB Output is correct