oj.uz

Submission #133955

# Submission time Handle Problem Language Result Execution time Memory
133955 2019-07-21T18:58:59 Z duality Wild Boar (JOI18_wild_boar) C++11
62 / 100
 18000 ms 660432 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;

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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 2 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 3 ms 1016 KB Output is correct
14 Correct 3 ms 1016 KB Output is correct
15 Correct 3 ms 1016 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 2 ms 1144 KB Output is correct
18 Correct 3 ms 1016 KB Output is correct
19 Correct 3 ms 1144 KB Output is correct
20 Correct 3 ms 1144 KB Output is correct
21 Correct 2 ms 1020 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 3 ms 1016 KB Output is correct
24 Correct 3 ms 1016 KB Output is correct
25 Correct 3 ms 1016 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 2 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 3 ms 1016 KB Output is correct
14 Correct 3 ms 1016 KB Output is correct
15 Correct 3 ms 1016 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 2 ms 1144 KB Output is correct
18 Correct 3 ms 1016 KB Output is correct
19 Correct 3 ms 1144 KB Output is correct
20 Correct 3 ms 1144 KB Output is correct
21 Correct 2 ms 1020 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 3 ms 1016 KB Output is correct
24 Correct 3 ms 1016 KB Output is correct
25 Correct 3 ms 1016 KB Output is correct
26 Correct 5 ms 1784 KB Output is correct
27 Correct 39 ms 5644 KB Output is correct
28 Correct 38 ms 5644 KB Output is correct
29 Correct 174 ms 13432 KB Output is correct
30 Correct 174 ms 13264 KB Output is correct
31 Correct 171 ms 13176 KB Output is correct
32 Correct 171 ms 13196 KB Output is correct
33 Correct 178 ms 15800 KB Output is correct
34 Correct 174 ms 15736 KB Output is correct
35 Correct 167 ms 15608 KB Output is correct
36 Correct 172 ms 15672 KB Output is correct
37 Correct 182 ms 15736 KB Output is correct
38 Correct 188 ms 18272 KB Output is correct
39 Correct 163 ms 18040 KB Output is correct
40 Correct 169 ms 18156 KB Output is correct
41 Correct 175 ms 18296 KB Output is correct
42 Correct 152 ms 19720 KB Output is correct
43 Correct 159 ms 21032 KB Output is correct
44 Correct 157 ms 20984 KB Output is correct
45 Correct 88 ms 23800 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 2 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 3 ms 1016 KB Output is correct
14 Correct 3 ms 1016 KB Output is correct
15 Correct 3 ms 1016 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 2 ms 1144 KB Output is correct
18 Correct 3 ms 1016 KB Output is correct
19 Correct 3 ms 1144 KB Output is correct
20 Correct 3 ms 1144 KB Output is correct
21 Correct 2 ms 1020 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 3 ms 1016 KB Output is correct
24 Correct 3 ms 1016 KB Output is correct
25 Correct 3 ms 1016 KB Output is correct
26 Correct 5 ms 1784 KB Output is correct
27 Correct 39 ms 5644 KB Output is correct
28 Correct 38 ms 5644 KB Output is correct
29 Correct 174 ms 13432 KB Output is correct
30 Correct 174 ms 13264 KB Output is correct
31 Correct 171 ms 13176 KB Output is correct
32 Correct 171 ms 13196 KB Output is correct
33 Correct 178 ms 15800 KB Output is correct
34 Correct 174 ms 15736 KB Output is correct
35 Correct 167 ms 15608 KB Output is correct
36 Correct 172 ms 15672 KB Output is correct
37 Correct 182 ms 15736 KB Output is correct
38 Correct 188 ms 18272 KB Output is correct
39 Correct 163 ms 18040 KB Output is correct
40 Correct 169 ms 18156 KB Output is correct
41 Correct 175 ms 18296 KB Output is correct
42 Correct 152 ms 19720 KB Output is correct
43 Correct 159 ms 21032 KB Output is correct
44 Correct 157 ms 20984 KB Output is correct
45 Correct 88 ms 23800 KB Output is correct
46 Correct 489 ms 29660 KB Output is correct
47 Correct 8002 ms 267732 KB Output is correct
48 Correct 8101 ms 341808 KB Output is correct
49 Correct 8292 ms 394616 KB Output is correct
50 Correct 8241 ms 394656 KB Output is correct
51 Correct 8272 ms 394572 KB Output is correct
52 Correct 8183 ms 394644 KB Output is correct
53 Correct 8220 ms 394660 KB Output is correct
54 Correct 8239 ms 394608 KB Output is correct
55 Correct 8194 ms 394744 KB Output is correct
56 Correct 8296 ms 422488 KB Output is correct
57 Correct 8286 ms 451444 KB Output is correct
58 Correct 8164 ms 480528 KB Output is correct
59 Correct 8055 ms 510544 KB Output is correct
60 Correct 7948 ms 541264 KB Output is correct
61 Correct 7764 ms 568632 KB Output is correct
62 Correct 7484 ms 596480 KB Output is correct
63 Correct 7024 ms 624964 KB Output is correct
64 Correct 2984 ms 660272 KB Output is correct
65 Correct 3010 ms 660208 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 2 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 3 ms 1016 KB Output is correct
14 Correct 3 ms 1016 KB Output is correct
15 Correct 3 ms 1016 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 2 ms 1144 KB Output is correct
18 Correct 3 ms 1016 KB Output is correct
19 Correct 3 ms 1144 KB Output is correct
20 Correct 3 ms 1144 KB Output is correct
21 Correct 2 ms 1020 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 3 ms 1016 KB Output is correct
24 Correct 3 ms 1016 KB Output is correct
25 Correct 3 ms 1016 KB Output is correct
26 Correct 5 ms 1784 KB Output is correct
27 Correct 39 ms 5644 KB Output is correct
28 Correct 38 ms 5644 KB Output is correct
29 Correct 174 ms 13432 KB Output is correct
30 Correct 174 ms 13264 KB Output is correct
31 Correct 171 ms 13176 KB Output is correct
32 Correct 171 ms 13196 KB Output is correct
33 Correct 178 ms 15800 KB Output is correct
34 Correct 174 ms 15736 KB Output is correct
35 Correct 167 ms 15608 KB Output is correct
36 Correct 172 ms 15672 KB Output is correct
37 Correct 182 ms 15736 KB Output is correct
38 Correct 188 ms 18272 KB Output is correct
39 Correct 163 ms 18040 KB Output is correct
40 Correct 169 ms 18156 KB Output is correct
41 Correct 175 ms 18296 KB Output is correct
42 Correct 152 ms 19720 KB Output is correct
43 Correct 159 ms 21032 KB Output is correct
44 Correct 157 ms 20984 KB Output is correct
45 Correct 88 ms 23800 KB Output is correct
46 Correct 489 ms 29660 KB Output is correct
47 Correct 8002 ms 267732 KB Output is correct
48 Correct 8101 ms 341808 KB Output is correct
49 Correct 8292 ms 394616 KB Output is correct
50 Correct 8241 ms 394656 KB Output is correct
51 Correct 8272 ms 394572 KB Output is correct
52 Correct 8183 ms 394644 KB Output is correct
53 Correct 8220 ms 394660 KB Output is correct
54 Correct 8239 ms 394608 KB Output is correct
55 Correct 8194 ms 394744 KB Output is correct
56 Correct 8296 ms 422488 KB Output is correct
57 Correct 8286 ms 451444 KB Output is correct
58 Correct 8164 ms 480528 KB Output is correct
59 Correct 8055 ms 510544 KB Output is correct
60 Correct 7948 ms 541264 KB Output is correct
61 Correct 7764 ms 568632 KB Output is correct
62 Correct 7484 ms 596480 KB Output is correct
63 Correct 7024 ms 624964 KB Output is correct
64 Correct 2984 ms 660272 KB Output is correct
65 Correct 3010 ms 660208 KB Output is correct
66 Correct 1700 ms 2464 KB Output is correct
67 Correct 2421 ms 190968 KB Output is correct
68 Correct 2898 ms 659392 KB Output is correct
69 Correct 4607 ms 660432 KB Output is correct
70 Execution timed out 18134 ms 660276 KB Time limit exceeded
71 Halted 0 ms 0 KB -