oj.uz

Submission #133980

# Submission time Handle Problem Language Result Execution time Memory
133980 2019-07-21T20:26:01 Z duality Wild Boar (JOI18_wild_boar) C++11
47 / 100
 10731 ms 1048580 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[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) {
    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 = 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] = 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;
    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].u][edges[j].v].pb((path){i,j,dist[i][j]+edges[i].w});
    }
    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 > 1e17) ? -1: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:177:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:178:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++)
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:127: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:129: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:134: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:187: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 94 ms 100984 KB Output is correct
2 Correct 96 ms 101112 KB Output is correct
3 Correct 95 ms 101112 KB Output is correct
4 Correct 96 ms 101240 KB Output is correct
5 Correct 95 ms 101112 KB Output is correct
6 Correct 96 ms 101112 KB Output is correct
7 Correct 97 ms 101112 KB Output is correct
8 Correct 97 ms 101112 KB Output is correct
9 Correct 96 ms 101112 KB Output is correct
10 Correct 96 ms 101112 KB Output is correct
11 Correct 96 ms 101112 KB Output is correct
12 Correct 100 ms 101112 KB Output is correct
13 Correct 106 ms 101156 KB Output is correct
14 Correct 105 ms 101140 KB Output is correct
15 Correct 98 ms 101112 KB Output is correct
16 Correct 96 ms 101112 KB Output is correct
17 Correct 94 ms 101148 KB Output is correct
18 Correct 95 ms 101112 KB Output is correct
19 Correct 94 ms 101112 KB Output is correct
20 Correct 94 ms 101112 KB Output is correct
21 Correct 97 ms 101116 KB Output is correct
22 Correct 99 ms 101164 KB Output is correct
23 Correct 95 ms 101084 KB Output is correct
24 Correct 94 ms 101240 KB Output is correct
25 Correct 95 ms 101112 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 100984 KB Output is correct
2 Correct 96 ms 101112 KB Output is correct
3 Correct 95 ms 101112 KB Output is correct
4 Correct 96 ms 101240 KB Output is correct
5 Correct 95 ms 101112 KB Output is correct
6 Correct 96 ms 101112 KB Output is correct
7 Correct 97 ms 101112 KB Output is correct
8 Correct 97 ms 101112 KB Output is correct
9 Correct 96 ms 101112 KB Output is correct
10 Correct 96 ms 101112 KB Output is correct
11 Correct 96 ms 101112 KB Output is correct
12 Correct 100 ms 101112 KB Output is correct
13 Correct 106 ms 101156 KB Output is correct
14 Correct 105 ms 101140 KB Output is correct
15 Correct 98 ms 101112 KB Output is correct
16 Correct 96 ms 101112 KB Output is correct
17 Correct 94 ms 101148 KB Output is correct
18 Correct 95 ms 101112 KB Output is correct
19 Correct 94 ms 101112 KB Output is correct
20 Correct 94 ms 101112 KB Output is correct
21 Correct 97 ms 101116 KB Output is correct
22 Correct 99 ms 101164 KB Output is correct
23 Correct 95 ms 101084 KB Output is correct
24 Correct 94 ms 101240 KB Output is correct
25 Correct 95 ms 101112 KB Output is correct
26 Correct 110 ms 101768 KB Output is correct
27 Correct 161 ms 108508 KB Output is correct
28 Correct 161 ms 107632 KB Output is correct
29 Correct 569 ms 134160 KB Output is correct
30 Correct 606 ms 133856 KB Output is correct
31 Correct 534 ms 133740 KB Output is correct
32 Correct 503 ms 133580 KB Output is correct
33 Correct 590 ms 136592 KB Output is correct
34 Correct 644 ms 136580 KB Output is correct
35 Correct 539 ms 135984 KB Output is correct
36 Correct 610 ms 136300 KB Output is correct
37 Correct 575 ms 136576 KB Output is correct
38 Correct 557 ms 139756 KB Output is correct
39 Correct 590 ms 139088 KB Output is correct
40 Correct 595 ms 139828 KB Output is correct
41 Correct 563 ms 139688 KB Output is correct
42 Correct 490 ms 141156 KB Output is correct
43 Correct 539 ms 143928 KB Output is correct
44 Correct 539 ms 143800 KB Output is correct
45 Correct 394 ms 138172 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 100984 KB Output is correct
2 Correct 96 ms 101112 KB Output is correct
3 Correct 95 ms 101112 KB Output is correct
4 Correct 96 ms 101240 KB Output is correct
5 Correct 95 ms 101112 KB Output is correct
6 Correct 96 ms 101112 KB Output is correct
7 Correct 97 ms 101112 KB Output is correct
8 Correct 97 ms 101112 KB Output is correct
9 Correct 96 ms 101112 KB Output is correct
10 Correct 96 ms 101112 KB Output is correct
11 Correct 96 ms 101112 KB Output is correct
12 Correct 100 ms 101112 KB Output is correct
13 Correct 106 ms 101156 KB Output is correct
14 Correct 105 ms 101140 KB Output is correct
15 Correct 98 ms 101112 KB Output is correct
16 Correct 96 ms 101112 KB Output is correct
17 Correct 94 ms 101148 KB Output is correct
18 Correct 95 ms 101112 KB Output is correct
19 Correct 94 ms 101112 KB Output is correct
20 Correct 94 ms 101112 KB Output is correct
21 Correct 97 ms 101116 KB Output is correct
22 Correct 99 ms 101164 KB Output is correct
23 Correct 95 ms 101084 KB Output is correct
24 Correct 94 ms 101240 KB Output is correct
25 Correct 95 ms 101112 KB Output is correct
26 Correct 110 ms 101768 KB Output is correct
27 Correct 161 ms 108508 KB Output is correct
28 Correct 161 ms 107632 KB Output is correct
29 Correct 569 ms 134160 KB Output is correct
30 Correct 606 ms 133856 KB Output is correct
31 Correct 534 ms 133740 KB Output is correct
32 Correct 503 ms 133580 KB Output is correct
33 Correct 590 ms 136592 KB Output is correct
34 Correct 644 ms 136580 KB Output is correct
35 Correct 539 ms 135984 KB Output is correct
36 Correct 610 ms 136300 KB Output is correct
37 Correct 575 ms 136576 KB Output is correct
38 Correct 557 ms 139756 KB Output is correct
39 Correct 590 ms 139088 KB Output is correct
40 Correct 595 ms 139828 KB Output is correct
41 Correct 563 ms 139688 KB Output is correct
42 Correct 490 ms 141156 KB Output is correct
43 Correct 539 ms 143928 KB Output is correct
44 Correct 539 ms 143800 KB Output is correct
45 Correct 394 ms 138172 KB Output is correct
46 Correct 591 ms 149712 KB Output is correct
47 Correct 9021 ms 694508 KB Output is correct
48 Correct 9386 ms 776548 KB Output is correct
49 Correct 10014 ms 849460 KB Output is correct
50 Correct 9907 ms 840208 KB Output is correct
51 Correct 9899 ms 829552 KB Output is correct
52 Correct 9610 ms 870232 KB Output is correct
53 Correct 9628 ms 870556 KB Output is correct
54 Correct 9739 ms 871000 KB Output is correct
55 Correct 9596 ms 870992 KB Output is correct
56 Correct 10016 ms 906916 KB Output is correct
57 Correct 10042 ms 935048 KB Output is correct
58 Correct 10405 ms 962788 KB Output is correct
59 Correct 10731 ms 1013052 KB Output is correct
60 Runtime error 7276 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 100984 KB Output is correct
2 Correct 96 ms 101112 KB Output is correct
3 Correct 95 ms 101112 KB Output is correct
4 Correct 96 ms 101240 KB Output is correct
5 Correct 95 ms 101112 KB Output is correct
6 Correct 96 ms 101112 KB Output is correct
7 Correct 97 ms 101112 KB Output is correct
8 Correct 97 ms 101112 KB Output is correct
9 Correct 96 ms 101112 KB Output is correct
10 Correct 96 ms 101112 KB Output is correct
11 Correct 96 ms 101112 KB Output is correct
12 Correct 100 ms 101112 KB Output is correct
13 Correct 106 ms 101156 KB Output is correct
14 Correct 105 ms 101140 KB Output is correct
15 Correct 98 ms 101112 KB Output is correct
16 Correct 96 ms 101112 KB Output is correct
17 Correct 94 ms 101148 KB Output is correct
18 Correct 95 ms 101112 KB Output is correct
19 Correct 94 ms 101112 KB Output is correct
20 Correct 94 ms 101112 KB Output is correct
21 Correct 97 ms 101116 KB Output is correct
22 Correct 99 ms 101164 KB Output is correct
23 Correct 95 ms 101084 KB Output is correct
24 Correct 94 ms 101240 KB Output is correct
25 Correct 95 ms 101112 KB Output is correct
26 Correct 110 ms 101768 KB Output is correct
27 Correct 161 ms 108508 KB Output is correct
28 Correct 161 ms 107632 KB Output is correct
29 Correct 569 ms 134160 KB Output is correct
30 Correct 606 ms 133856 KB Output is correct
31 Correct 534 ms 133740 KB Output is correct
32 Correct 503 ms 133580 KB Output is correct
33 Correct 590 ms 136592 KB Output is correct
34 Correct 644 ms 136580 KB Output is correct
35 Correct 539 ms 135984 KB Output is correct
36 Correct 610 ms 136300 KB Output is correct
37 Correct 575 ms 136576 KB Output is correct
38 Correct 557 ms 139756 KB Output is correct
39 Correct 590 ms 139088 KB Output is correct
40 Correct 595 ms 139828 KB Output is correct
41 Correct 563 ms 139688 KB Output is correct
42 Correct 490 ms 141156 KB Output is correct
43 Correct 539 ms 143928 KB Output is correct
44 Correct 539 ms 143800 KB Output is correct
45 Correct 394 ms 138172 KB Output is correct
46 Correct 591 ms 149712 KB Output is correct
47 Correct 9021 ms 694508 KB Output is correct
48 Correct 9386 ms 776548 KB Output is correct
49 Correct 10014 ms 849460 KB Output is correct
50 Correct 9907 ms 840208 KB Output is correct
51 Correct 9899 ms 829552 KB Output is correct
52 Correct 9610 ms 870232 KB Output is correct
53 Correct 9628 ms 870556 KB Output is correct
54 Correct 9739 ms 871000 KB Output is correct
55 Correct 9596 ms 870992 KB Output is correct
56 Correct 10016 ms 906916 KB Output is correct
57 Correct 10042 ms 935048 KB Output is correct
58 Correct 10405 ms 962788 KB Output is correct
59 Correct 10731 ms 1013052 KB Output is correct
60 Runtime error 7276 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Halted 0 ms 0 KB -