oj.uz

Submission #133981

# Submission time Handle Problem Language Result Execution time Memory
133981 2019-07-21T20:31:20 Z duality Wild Boar (JOI18_wild_boar) C++11
47 / 100
 10694 ms 1048576 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 < num; i++) adjList[i].clear(),adjList[i].shrink_to_fit();
    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: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: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:188: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 102 ms 101112 KB Output is correct
2 Correct 95 ms 101112 KB Output is correct
3 Correct 96 ms 101112 KB Output is correct
4 Correct 95 ms 101112 KB Output is correct
5 Correct 94 ms 101112 KB Output is correct
6 Correct 95 ms 101112 KB Output is correct
7 Correct 95 ms 101112 KB Output is correct
8 Correct 95 ms 101112 KB Output is correct
9 Correct 95 ms 101112 KB Output is correct
10 Correct 95 ms 101112 KB Output is correct
11 Correct 95 ms 101240 KB Output is correct
12 Correct 96 ms 101164 KB Output is correct
13 Correct 95 ms 101116 KB Output is correct
14 Correct 96 ms 101112 KB Output is correct
15 Correct 113 ms 101112 KB Output is correct
16 Correct 115 ms 101268 KB Output is correct
17 Correct 113 ms 101212 KB Output is correct
18 Correct 114 ms 101112 KB Output is correct
19 Correct 110 ms 101112 KB Output is correct
20 Correct 95 ms 101112 KB Output is correct
21 Correct 94 ms 101112 KB Output is correct
22 Correct 96 ms 101240 KB Output is correct
23 Correct 96 ms 101164 KB Output is correct
24 Correct 95 ms 101112 KB Output is correct
25 Correct 96 ms 101112 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 101112 KB Output is correct
2 Correct 95 ms 101112 KB Output is correct
3 Correct 96 ms 101112 KB Output is correct
4 Correct 95 ms 101112 KB Output is correct
5 Correct 94 ms 101112 KB Output is correct
6 Correct 95 ms 101112 KB Output is correct
7 Correct 95 ms 101112 KB Output is correct
8 Correct 95 ms 101112 KB Output is correct
9 Correct 95 ms 101112 KB Output is correct
10 Correct 95 ms 101112 KB Output is correct
11 Correct 95 ms 101240 KB Output is correct
12 Correct 96 ms 101164 KB Output is correct
13 Correct 95 ms 101116 KB Output is correct
14 Correct 96 ms 101112 KB Output is correct
15 Correct 113 ms 101112 KB Output is correct
16 Correct 115 ms 101268 KB Output is correct
17 Correct 113 ms 101212 KB Output is correct
18 Correct 114 ms 101112 KB Output is correct
19 Correct 110 ms 101112 KB Output is correct
20 Correct 95 ms 101112 KB Output is correct
21 Correct 94 ms 101112 KB Output is correct
22 Correct 96 ms 101240 KB Output is correct
23 Correct 96 ms 101164 KB Output is correct
24 Correct 95 ms 101112 KB Output is correct
25 Correct 96 ms 101112 KB Output is correct
26 Correct 98 ms 101752 KB Output is correct
27 Correct 144 ms 108256 KB Output is correct
28 Correct 142 ms 107828 KB Output is correct
29 Correct 573 ms 134080 KB Output is correct
30 Correct 599 ms 133712 KB Output is correct
31 Correct 529 ms 133752 KB Output is correct
32 Correct 543 ms 133676 KB Output is correct
33 Correct 571 ms 136732 KB Output is correct
34 Correct 608 ms 136680 KB Output is correct
35 Correct 485 ms 135892 KB Output is correct
36 Correct 610 ms 136092 KB Output is correct
37 Correct 586 ms 136552 KB Output is correct
38 Correct 612 ms 139848 KB Output is correct
39 Correct 583 ms 139240 KB Output is correct
40 Correct 594 ms 139736 KB Output is correct
41 Correct 577 ms 139852 KB Output is correct
42 Correct 540 ms 141100 KB Output is correct
43 Correct 592 ms 143800 KB Output is correct
44 Correct 538 ms 143756 KB Output is correct
45 Correct 413 ms 138292 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 101112 KB Output is correct
2 Correct 95 ms 101112 KB Output is correct
3 Correct 96 ms 101112 KB Output is correct
4 Correct 95 ms 101112 KB Output is correct
5 Correct 94 ms 101112 KB Output is correct
6 Correct 95 ms 101112 KB Output is correct
7 Correct 95 ms 101112 KB Output is correct
8 Correct 95 ms 101112 KB Output is correct
9 Correct 95 ms 101112 KB Output is correct
10 Correct 95 ms 101112 KB Output is correct
11 Correct 95 ms 101240 KB Output is correct
12 Correct 96 ms 101164 KB Output is correct
13 Correct 95 ms 101116 KB Output is correct
14 Correct 96 ms 101112 KB Output is correct
15 Correct 113 ms 101112 KB Output is correct
16 Correct 115 ms 101268 KB Output is correct
17 Correct 113 ms 101212 KB Output is correct
18 Correct 114 ms 101112 KB Output is correct
19 Correct 110 ms 101112 KB Output is correct
20 Correct 95 ms 101112 KB Output is correct
21 Correct 94 ms 101112 KB Output is correct
22 Correct 96 ms 101240 KB Output is correct
23 Correct 96 ms 101164 KB Output is correct
24 Correct 95 ms 101112 KB Output is correct
25 Correct 96 ms 101112 KB Output is correct
26 Correct 98 ms 101752 KB Output is correct
27 Correct 144 ms 108256 KB Output is correct
28 Correct 142 ms 107828 KB Output is correct
29 Correct 573 ms 134080 KB Output is correct
30 Correct 599 ms 133712 KB Output is correct
31 Correct 529 ms 133752 KB Output is correct
32 Correct 543 ms 133676 KB Output is correct
33 Correct 571 ms 136732 KB Output is correct
34 Correct 608 ms 136680 KB Output is correct
35 Correct 485 ms 135892 KB Output is correct
36 Correct 610 ms 136092 KB Output is correct
37 Correct 586 ms 136552 KB Output is correct
38 Correct 612 ms 139848 KB Output is correct
39 Correct 583 ms 139240 KB Output is correct
40 Correct 594 ms 139736 KB Output is correct
41 Correct 577 ms 139852 KB Output is correct
42 Correct 540 ms 141100 KB Output is correct
43 Correct 592 ms 143800 KB Output is correct
44 Correct 538 ms 143756 KB Output is correct
45 Correct 413 ms 138292 KB Output is correct
46 Correct 611 ms 149644 KB Output is correct
47 Correct 8821 ms 694608 KB Output is correct
48 Correct 9386 ms 775896 KB Output is correct
49 Correct 10062 ms 848904 KB Output is correct
50 Correct 9774 ms 839832 KB Output is correct
51 Correct 10095 ms 828728 KB Output is correct
52 Correct 9642 ms 869932 KB Output is correct
53 Correct 9699 ms 870120 KB Output is correct
54 Correct 9666 ms 870552 KB Output is correct
55 Correct 9573 ms 870692 KB Output is correct
56 Correct 9827 ms 906712 KB Output is correct
57 Correct 10098 ms 935008 KB Output is correct
58 Correct 10403 ms 963048 KB Output is correct
59 Correct 10694 ms 1012828 KB Output is correct
60 Runtime error 7334 ms 1048576 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 102 ms 101112 KB Output is correct
2 Correct 95 ms 101112 KB Output is correct
3 Correct 96 ms 101112 KB Output is correct
4 Correct 95 ms 101112 KB Output is correct
5 Correct 94 ms 101112 KB Output is correct
6 Correct 95 ms 101112 KB Output is correct
7 Correct 95 ms 101112 KB Output is correct
8 Correct 95 ms 101112 KB Output is correct
9 Correct 95 ms 101112 KB Output is correct
10 Correct 95 ms 101112 KB Output is correct
11 Correct 95 ms 101240 KB Output is correct
12 Correct 96 ms 101164 KB Output is correct
13 Correct 95 ms 101116 KB Output is correct
14 Correct 96 ms 101112 KB Output is correct
15 Correct 113 ms 101112 KB Output is correct
16 Correct 115 ms 101268 KB Output is correct
17 Correct 113 ms 101212 KB Output is correct
18 Correct 114 ms 101112 KB Output is correct
19 Correct 110 ms 101112 KB Output is correct
20 Correct 95 ms 101112 KB Output is correct
21 Correct 94 ms 101112 KB Output is correct
22 Correct 96 ms 101240 KB Output is correct
23 Correct 96 ms 101164 KB Output is correct
24 Correct 95 ms 101112 KB Output is correct
25 Correct 96 ms 101112 KB Output is correct
26 Correct 98 ms 101752 KB Output is correct
27 Correct 144 ms 108256 KB Output is correct
28 Correct 142 ms 107828 KB Output is correct
29 Correct 573 ms 134080 KB Output is correct
30 Correct 599 ms 133712 KB Output is correct
31 Correct 529 ms 133752 KB Output is correct
32 Correct 543 ms 133676 KB Output is correct
33 Correct 571 ms 136732 KB Output is correct
34 Correct 608 ms 136680 KB Output is correct
35 Correct 485 ms 135892 KB Output is correct
36 Correct 610 ms 136092 KB Output is correct
37 Correct 586 ms 136552 KB Output is correct
38 Correct 612 ms 139848 KB Output is correct
39 Correct 583 ms 139240 KB Output is correct
40 Correct 594 ms 139736 KB Output is correct
41 Correct 577 ms 139852 KB Output is correct
42 Correct 540 ms 141100 KB Output is correct
43 Correct 592 ms 143800 KB Output is correct
44 Correct 538 ms 143756 KB Output is correct
45 Correct 413 ms 138292 KB Output is correct
46 Correct 611 ms 149644 KB Output is correct
47 Correct 8821 ms 694608 KB Output is correct
48 Correct 9386 ms 775896 KB Output is correct
49 Correct 10062 ms 848904 KB Output is correct
50 Correct 9774 ms 839832 KB Output is correct
51 Correct 10095 ms 828728 KB Output is correct
52 Correct 9642 ms 869932 KB Output is correct
53 Correct 9699 ms 870120 KB Output is correct
54 Correct 9666 ms 870552 KB Output is correct
55 Correct 9573 ms 870692 KB Output is correct
56 Correct 9827 ms 906712 KB Output is correct
57 Correct 10098 ms 935008 KB Output is correct
58 Correct 10403 ms 963048 KB Output is correct
59 Correct 10694 ms 1012828 KB Output is correct
60 Runtime error 7334 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Halted 0 ms 0 KB -