제출 #171365

#제출 시각아이디문제언어결과실행 시간메모리
171365alexandra_udristoiu전선 연결 (IOI17_wiring)C++14
55 / 100
48 ms9208 KiB
#include<iostream> #include<vector> #include "wiring.h" #define DIM 200005 #define f first #define s second using namespace std; static long long d[DIM], sp[DIM]; pair<int, int> v[DIM]; pair<int, long long> dq[DIM]; long long min_total_length(vector<int> r, vector<int> b) { int n, m, i, j, curr, prv, ind, p, u; long long sum1, sum2, minim; n = r.size(); m = b.size(); i = j = 0; while(i < n && j < m){ if(r[i] < b[j]){ v[i + j + 1] = make_pair(r[i], 0); i++; } else{ v[i + j + 1] = make_pair(b[j], 1); j++; } } for(; i < n; i++){ v[i + j + 1] = make_pair(r[i], 0); } for(; j < m; j++){ v[i + j + 1] = make_pair(b[j], 1); } n += m; for(i = 1; i <= n; i++){ sp[i] = sp[i - 1] + v[i].f; } prv = 1; sum1 = v[1].f; sum2 = 0; for(i = 2; i <= n; i++){ if(v[i].s != v[i - 1].s){ curr = i; break; } else{ d[i] = 10000000000000LL; sum1 += v[i].f; } } for(; i <= n; i++){ sum2 += v[i].f; d[i] = sum2 - sum1; if(i - curr + 1 < curr - prv){ d[i] += ( (curr - prv) - (i - curr + 1) ) * 1LL * v[curr].f; } else{ d[i] -= ( (i - curr + 1) - (curr - prv) ) * 1LL * v[curr - 1].f; } if(v[i + 1].s != v[i].s){ break; } } for(i = i + 1; i <= n; i++){ if(v[i - 1].s != v[i].s){ prv = curr; curr = i; p = 1; u = 0; for(j = i - 1; j >= prv; j--){ if(d[j - 1] == 0){ break; } sum1 = d[j - 1] - sp[i - 1] + sp[j - 1] + v[i].f * 1LL * (i - j); while(p <= u && dq[u].s > sum1){ u--; } dq[++u] = make_pair(j, sum1); } minim = min(d[i - 1], d[i - 2]) + v[i].f - v[i - 1].f; if(dq[p].f == i - 1){ p++; } if(p <= u){ d[i] = min(minim, dq[p].s); } else{ d[i] = minim; } ind = i - 1; } else{ minim += v[i].f - v[curr - 1].f; if(i - curr + 1 <= curr - prv){ ind--; minim = min(minim, d[ind - 1] + sp[i] - sp[curr - 1] - sp[curr - 1] + sp[ind - 1]); if(dq[p].f == ind){ p++; } } if(p <= u){ d[i] = min(minim, dq[p].s + sp[i] - sp[curr] - v[curr].f * 1LL * (i - curr) ); } else{ d[i] = minim; } } } return d[n]; }

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:92:19: warning: 'minim' may be used uninitialized in this function [-Wmaybe-uninitialized]
             minim += v[i].f - v[curr - 1].f;
                   ^
wiring.cpp:100:13: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if(p <= u){
             ^~
wiring.cpp:5:11: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
 #define f first
           ^~~~~
wiring.cpp:12:37: note: 'p' was declared here
     int n, m, i, j, curr, prv, ind, p, u;
                                     ^
wiring.cpp:95:42: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 minim = min(minim, d[ind - 1] + sp[i] - sp[curr - 1] - sp[curr - 1] + sp[ind - 1]);
                                      ~~~~^~~
wiring.cpp:69:30: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
             for(j = i - 1; j >= prv; j--){
                            ~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...