oj.uz

답안 #133972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
133972 2019-07-21T19:57:41 Z duality Wild Boar (JOI18_wild_boar) C++11
12 / 100
 3528 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 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) {
    if (v.empty()) return 0;
    int i;
    vector<path> v2;
    sort(v.begin(),v.end(),comp);
    return 0;
    for (i = 1; i < v.size(); i++) {
        if ((v[i].eu == v[0].eu) && (v[i].ev != v[0].ev)) break;
    }
    int p = (i < v.size()) ? i:0;
    v2.pb(v[0]),v2.pb(v[p]);
    for (i = 1; i < v.size(); i++) {
        if (v[i].eu != v[0].eu) break;
    }
    int q = (i < v.size()) ? i:0;
    int r = -1;
    for (i = 1; i < v.size(); i++) {
        if ((v[i].eu == v[q].eu) && (v[i].ev != v[q].ev)) {
            r = i;
            break;
        }
    }
    v2.pb(v[q]);
    if (r != -1) v2.pb(v[r]);
    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].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;
}
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].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:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     int p = (i < v.size()) ? i:0;
              ~~^~~~~~~~~~
wild_boar.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     int q = (i < v.size()) ? i:0;
              ~~^~~~~~~~~~
wild_boar.cpp:69: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:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < a.size(); i++) {
                 ~~^~~~~~~~~~
wild_boar.cpp:85: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:134:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) {
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:139:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < v.size(); j++) {
                     ~~^~~~~~~~~~
wild_boar.cpp:140:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k = 0; k < nodes.size(); k++) {
                         ~~^~~~~~~~~~~~~~
wild_boar.cpp:143:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (k < nodes.size()) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:151:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:160:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < adjList[u].size(); j++) {
                         ~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:168: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:170:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wild_boar.cpp:171:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < edges.size(); j++) paths[edges[i].v][edges[j].v].pb((path){i,j,dist[i][j]});
                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:120: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:122: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:127: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:179: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

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 105320 KB Output is correct
2 Correct 2387 ms 397452 KB Output is correct
3 Correct 2370 ms 364724 KB Output is correct
4 Correct 426 ms 170184 KB Output is correct
5 Correct 333 ms 150544 KB Output is correct
6 Correct 662 ms 167528 KB Output is correct
7 Correct 1115 ms 217512 KB Output is correct
8 Correct 158 ms 113096 KB Output is correct
9 Correct 146 ms 113580 KB Output is correct
10 Correct 229 ms 124304 KB Output is correct
11 Correct 129 ms 108204 KB Output is correct
12 Correct 129 ms 110280 KB Output is correct
13 Correct 158 ms 113172 KB Output is correct
14 Correct 128 ms 110316 KB Output is correct
15 Correct 111 ms 104472 KB Output is correct
16 Correct 113 ms 104828 KB Output is correct
17 Correct 121 ms 107504 KB Output is correct
18 Correct 109 ms 104596 KB Output is correct
19 Correct 109 ms 104132 KB Output is correct
20 Correct 104 ms 103240 KB Output is correct
21 Correct 3490 ms 517712 KB Output is correct
22 Correct 2373 ms 517740 KB Output is correct
23 Correct 2368 ms 517676 KB Output is correct
24 Correct 2396 ms 550212 KB Output is correct
25 Correct 3528 ms 517692 KB Output is correct

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 105320 KB Output is correct
2 Correct 2387 ms 397452 KB Output is correct
3 Correct 2370 ms 364724 KB Output is correct
4 Correct 426 ms 170184 KB Output is correct
5 Correct 333 ms 150544 KB Output is correct
6 Correct 662 ms 167528 KB Output is correct
7 Correct 1115 ms 217512 KB Output is correct
8 Correct 158 ms 113096 KB Output is correct
9 Correct 146 ms 113580 KB Output is correct
10 Correct 229 ms 124304 KB Output is correct
11 Correct 129 ms 108204 KB Output is correct
12 Correct 129 ms 110280 KB Output is correct
13 Correct 158 ms 113172 KB Output is correct
14 Correct 128 ms 110316 KB Output is correct
15 Correct 111 ms 104472 KB Output is correct
16 Correct 113 ms 104828 KB Output is correct
17 Correct 121 ms 107504 KB Output is correct
18 Correct 109 ms 104596 KB Output is correct
19 Correct 109 ms 104132 KB Output is correct
20 Correct 104 ms 103240 KB Output is correct
21 Correct 3490 ms 517712 KB Output is correct
22 Correct 2373 ms 517740 KB Output is correct
23 Correct 2368 ms 517676 KB Output is correct
24 Correct 2396 ms 550212 KB Output is correct
25 Correct 3528 ms 517692 KB Output is correct
26 Runtime error 1956 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

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 105320 KB Output is correct
2 Correct 2387 ms 397452 KB Output is correct
3 Correct 2370 ms 364724 KB Output is correct
4 Correct 426 ms 170184 KB Output is correct
5 Correct 333 ms 150544 KB Output is correct
6 Correct 662 ms 167528 KB Output is correct
7 Correct 1115 ms 217512 KB Output is correct
8 Correct 158 ms 113096 KB Output is correct
9 Correct 146 ms 113580 KB Output is correct
10 Correct 229 ms 124304 KB Output is correct
11 Correct 129 ms 108204 KB Output is correct
12 Correct 129 ms 110280 KB Output is correct
13 Correct 158 ms 113172 KB Output is correct
14 Correct 128 ms 110316 KB Output is correct
15 Correct 111 ms 104472 KB Output is correct
16 Correct 113 ms 104828 KB Output is correct
17 Correct 121 ms 107504 KB Output is correct
18 Correct 109 ms 104596 KB Output is correct
19 Correct 109 ms 104132 KB Output is correct
20 Correct 104 ms 103240 KB Output is correct
21 Correct 3490 ms 517712 KB Output is correct
22 Correct 2373 ms 517740 KB Output is correct
23 Correct 2368 ms 517676 KB Output is correct
24 Correct 2396 ms 550212 KB Output is correct
25 Correct 3528 ms 517692 KB Output is correct
26 Runtime error 1956 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

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 105320 KB Output is correct
2 Correct 2387 ms 397452 KB Output is correct
3 Correct 2370 ms 364724 KB Output is correct
4 Correct 426 ms 170184 KB Output is correct
5 Correct 333 ms 150544 KB Output is correct
6 Correct 662 ms 167528 KB Output is correct
7 Correct 1115 ms 217512 KB Output is correct
8 Correct 158 ms 113096 KB Output is correct
9 Correct 146 ms 113580 KB Output is correct
10 Correct 229 ms 124304 KB Output is correct
11 Correct 129 ms 108204 KB Output is correct
12 Correct 129 ms 110280 KB Output is correct
13 Correct 158 ms 113172 KB Output is correct
14 Correct 128 ms 110316 KB Output is correct
15 Correct 111 ms 104472 KB Output is correct
16 Correct 113 ms 104828 KB Output is correct
17 Correct 121 ms 107504 KB Output is correct
18 Correct 109 ms 104596 KB Output is correct
19 Correct 109 ms 104132 KB Output is correct
20 Correct 104 ms 103240 KB Output is correct
21 Correct 3490 ms 517712 KB Output is correct
22 Correct 2373 ms 517740 KB Output is correct
23 Correct 2368 ms 517676 KB Output is correct
24 Correct 2396 ms 550212 KB Output is correct
25 Correct 3528 ms 517692 KB Output is correct
26 Runtime error 1956 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -