oj.uz

Submission #133976

# Submission time Handle Problem Language Result Execution time Memory
133976 2019-07-21T20:17:31 Z duality Wild Boar (JOI18_wild_boar) C++11
12 / 100
 2798 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) {
        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];
struct path { int e,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;
    return 0;
    v2.pb(v[0]);
    for (i = 1; i < v.size(); i++) {
        if ((v[i].e != v[0].e) && (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].e != v[0].e) {
            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].e != v[m1].e)) 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);
    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 (a[i].ev == b[j].eu) c.pb((path){a[i].e,a[i].eu,b[j].ev,min(a[i].d+b[j].d,(LLI) 1e18)});
        }
    }
    shorten(c);
    return c;
}
vector<path> tree2[1 << 18];
int build2(int s,int e,int i) {
    if (s == e) {
        tree2[i] = paths[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[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;
}
vi vv[2001];
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++) vv[edges[i].v].pb(i);
    for (i = 0; i < edges.size(); i++) {
        for (j = 0; j < edges.size(); j++) {
            for (k = 0; k < vv[edges[i].u].size(); k++) {
                if (dist[vv[edges[i].u][k]][j] == dist[i][j]+edges[i].w)
                    paths[edges[i].u][edges[j].v].pb((path){i,vv[edges[i].u][k],j,dist[vv[edges[i].u][k]][j]});
            }
            //paths[edges[i].v][edges[j].v].pb((path){i,j,dist[i][j]});
        }
    }
    for (i = 0; i <= N; i++) {
        for (j = 0; j <= N; j++) shorten(paths[i][j]);
    }

    build2(1,L-1,0);
    for (i = 0; i < T; i++) {
        scanf("%d %d",&P,&Q);
        P--,Q--;
        X[P] = Q;
        if (P > 0) update2(1,L-1,P,0);
        if (P < L-1) update2(1,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:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:76: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:142:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < v.size(); j++) {
                     ~~^~~~~~~~~~
wild_boar.cpp:148:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k = 0; k < nodes.size(); k++) {
                         ~~^~~~~~~~~~~~~~
wild_boar.cpp:151:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (k < nodes.size()) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:159:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:168:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < adjList[u].size(); j++) {
                         ~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:176: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++) vv[edges[i].v].pb(i);
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:179:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:180:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:181:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k = 0; k < vv[edges[i].u].size(); k++) {
                         ~~^~~~~~~~~~~~~~~~~~~~~~~
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:194: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 113 ms 101112 KB Output is correct
2 Correct 1434 ms 200576 KB Output is correct
3 Correct 1420 ms 200624 KB Output is correct
4 Correct 217 ms 119412 KB Output is correct
5 Correct 180 ms 119740 KB Output is correct
6 Correct 405 ms 145120 KB Output is correct
7 Correct 1352 ms 256092 KB Output is correct
8 Correct 102 ms 102772 KB Output is correct
9 Correct 102 ms 102524 KB Output is correct
10 Correct 109 ms 103564 KB Output is correct
11 Correct 96 ms 101816 KB Output is correct
12 Correct 101 ms 102136 KB Output is correct
13 Correct 101 ms 102300 KB Output is correct
14 Correct 105 ms 103624 KB Output is correct
15 Correct 96 ms 101444 KB Output is correct
16 Correct 96 ms 101560 KB Output is correct
17 Correct 98 ms 101880 KB Output is correct
18 Correct 95 ms 101368 KB Output is correct
19 Correct 95 ms 101240 KB Output is correct
20 Correct 95 ms 101240 KB Output is correct
21 Correct 1639 ms 269256 KB Output is correct
22 Correct 1599 ms 392156 KB Output is correct
23 Correct 967 ms 259164 KB Output is correct
24 Correct 1242 ms 285484 KB Output is correct
25 Correct 2798 ms 413976 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 101112 KB Output is correct
2 Correct 1434 ms 200576 KB Output is correct
3 Correct 1420 ms 200624 KB Output is correct
4 Correct 217 ms 119412 KB Output is correct
5 Correct 180 ms 119740 KB Output is correct
6 Correct 405 ms 145120 KB Output is correct
7 Correct 1352 ms 256092 KB Output is correct
8 Correct 102 ms 102772 KB Output is correct
9 Correct 102 ms 102524 KB Output is correct
10 Correct 109 ms 103564 KB Output is correct
11 Correct 96 ms 101816 KB Output is correct
12 Correct 101 ms 102136 KB Output is correct
13 Correct 101 ms 102300 KB Output is correct
14 Correct 105 ms 103624 KB Output is correct
15 Correct 96 ms 101444 KB Output is correct
16 Correct 96 ms 101560 KB Output is correct
17 Correct 98 ms 101880 KB Output is correct
18 Correct 95 ms 101368 KB Output is correct
19 Correct 95 ms 101240 KB Output is correct
20 Correct 95 ms 101240 KB Output is correct
21 Correct 1639 ms 269256 KB Output is correct
22 Correct 1599 ms 392156 KB Output is correct
23 Correct 967 ms 259164 KB Output is correct
24 Correct 1242 ms 285484 KB Output is correct
25 Correct 2798 ms 413976 KB Output is correct
26 Runtime error 2347 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 101112 KB Output is correct
2 Correct 1434 ms 200576 KB Output is correct
3 Correct 1420 ms 200624 KB Output is correct
4 Correct 217 ms 119412 KB Output is correct
5 Correct 180 ms 119740 KB Output is correct
6 Correct 405 ms 145120 KB Output is correct
7 Correct 1352 ms 256092 KB Output is correct
8 Correct 102 ms 102772 KB Output is correct
9 Correct 102 ms 102524 KB Output is correct
10 Correct 109 ms 103564 KB Output is correct
11 Correct 96 ms 101816 KB Output is correct
12 Correct 101 ms 102136 KB Output is correct
13 Correct 101 ms 102300 KB Output is correct
14 Correct 105 ms 103624 KB Output is correct
15 Correct 96 ms 101444 KB Output is correct
16 Correct 96 ms 101560 KB Output is correct
17 Correct 98 ms 101880 KB Output is correct
18 Correct 95 ms 101368 KB Output is correct
19 Correct 95 ms 101240 KB Output is correct
20 Correct 95 ms 101240 KB Output is correct
21 Correct 1639 ms 269256 KB Output is correct
22 Correct 1599 ms 392156 KB Output is correct
23 Correct 967 ms 259164 KB Output is correct
24 Correct 1242 ms 285484 KB Output is correct
25 Correct 2798 ms 413976 KB Output is correct
26 Runtime error 2347 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 101112 KB Output is correct
2 Correct 1434 ms 200576 KB Output is correct
3 Correct 1420 ms 200624 KB Output is correct
4 Correct 217 ms 119412 KB Output is correct
5 Correct 180 ms 119740 KB Output is correct
6 Correct 405 ms 145120 KB Output is correct
7 Correct 1352 ms 256092 KB Output is correct
8 Correct 102 ms 102772 KB Output is correct
9 Correct 102 ms 102524 KB Output is correct
10 Correct 109 ms 103564 KB Output is correct
11 Correct 96 ms 101816 KB Output is correct
12 Correct 101 ms 102136 KB Output is correct
13 Correct 101 ms 102300 KB Output is correct
14 Correct 105 ms 103624 KB Output is correct
15 Correct 96 ms 101444 KB Output is correct
16 Correct 96 ms 101560 KB Output is correct
17 Correct 98 ms 101880 KB Output is correct
18 Correct 95 ms 101368 KB Output is correct
19 Correct 95 ms 101240 KB Output is correct
20 Correct 95 ms 101240 KB Output is correct
21 Correct 1639 ms 269256 KB Output is correct
22 Correct 1599 ms 392156 KB Output is correct
23 Correct 967 ms 259164 KB Output is correct
24 Correct 1242 ms 285484 KB Output is correct
25 Correct 2798 ms 413976 KB Output is correct
26 Runtime error 2347 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -