oj.uz

Submission #133938

# Submission time Handle Problem Language Result Execution time Memory
133938 2019-07-21T18:40:05 Z duality Wild Boar (JOI18_wild_boar) C++11
12 / 100
 68 ms 4728 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;
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});
    for (i = 0; i < edges.size(); i++) fill(dist[i],dist[i]+edges.size(),1e18),dist[i][i] = 0;
    for (i = 0; i < edges.size(); i++) {
        for (j = 0; j < edges.size(); j++) {
            if ((edges[i].v == edges[j].u) && (edges[i].u != edges[j].v)) dist[i][j] = edges[j].w;
        }
    }
    for (k = 0; k < edges.size(); k++) {
        for (i = 0; i < edges.size(); i++) {
            for (j = 0; j < edges.size(); j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][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 = b[0].first,ne1 = b[0].second;
            nd2 = b[1].first,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:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) fill(dist[i],dist[i]+edges.size(),1e18),dist[i][i] = 0;
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (k = 0; k < edges.size(); k++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < edges.size(); i++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:38:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < edges.size(); j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
                         ~~^~~~~~~~~~~~~~
wild_boar.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:19: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:21: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:26: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:56: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 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 2 ms 632 KB Output is correct
20 Correct 2 ms 632 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 2 ms 504 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 2 ms 504 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 2 ms 632 KB Output is correct
20 Correct 2 ms 632 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 2 ms 504 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 4 ms 1272 KB Output is correct
27 Incorrect 68 ms 4728 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 2 ms 632 KB Output is correct
20 Correct 2 ms 632 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 2 ms 504 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 4 ms 1272 KB Output is correct
27 Incorrect 68 ms 4728 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 2 ms 632 KB Output is correct
20 Correct 2 ms 632 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 2 ms 504 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 4 ms 1272 KB Output is correct
27 Incorrect 68 ms 4728 KB Output isn't correct
28 Halted 0 ms 0 KB -