제출 #962172

#제출 시각아이디문제언어결과실행 시간메모리
962172stev2005꿈 (IOI13_dreaming)C++17
0 / 100
1051 ms9564 KiB
#include "dreaming.h" #include<bits/stdc++.h> using namespace std; const int maxn = (1<<17), inf = (1<<30); int n, m, lprice; struct edge{ int ver, cost; edge(){ ver = -1; cost = 0; } edge(int _ver, int _cost){ ver = _ver; cost = _cost; } bool operator<(const edge &other) const{ return cost > other.cost; } }; struct diamgr{ int s, f; int cost, sum1, sum2; diamgr(){ /*mid =*/ s = f = -1; cost = sum1 = sum2 = -1; } diamgr(int _s, int _f, int _cost, int _sum1, int _sum2){ s = _s; f = _f; //mid = _mid; cost = _cost; sum1 = _sum1; sum2 = _sum2; } }; vector <edge> v[maxn]; bool used[maxn]; bool checkver[maxn]; int parsum[maxn], parsum1[maxn], parsum2[maxn]; int anscost; int d[maxn]; int par[maxn], costpar[maxn]; inline void init_vectors(int *a, int *b, int *t){ for (int i = 0; i < m; ++i){ v[a[i]].push_back(edge(b[i], t[i])); v[b[i]].push_back(edge(b[i], t[i])); //cerr << a[i] << " " << b[i] << " " << t[i] << endl; } } int Dijkstra(int beg){ memset(used, 0, sizeof(used)); memset(par, -1, sizeof(par)); used[beg] = 1; checkver[beg] = 1; for (int i = 0; i < n; ++i) d[i] = inf; d[beg] = 0; costpar[beg] = 0; par[beg] = -1; priority_queue<edge> q; q.push(edge(beg, 0)); int lastpopped = -1; while (!q.empty()){ edge cur = q.top(); q.pop(); lastpopped = cur.ver; if (cur.cost <= d[cur.ver]){ used[cur.ver] = 1; checkver[cur.ver] = 1; for (int i = 0; i < (int)v[cur.ver].size(); ++i){ edge nb = v[cur.ver][i]; if (cur.cost + nb.cost < d[nb.ver]){ par[nb.ver] = cur.ver; costpar[nb.ver] = nb.cost; d[nb.ver] = cur.cost + nb.cost; nb.cost = d[nb.ver]; q.push(nb); } } } } return lastpopped; } int init_parsums(int s, int f, int *parsum){ int cur = f, prev = -1; int cnt = 1; while (cur != s){ parsum[cnt] = parsum[cnt - 1] + costpar[cur]; cur = par[cur]; cnt++; } return cnt; } pair<int, int> find_mindif(int n, int *parsum){ if (n == 1) return {0, 0}; if (n == 2) return {0, parsum[1]}; int sum1 = -(1<<30) + 10, sum2 = (1<<30) - 10; for (int i = 0; i < n; ++i){ int cursum1 = parsum[i]; int cursum2 = parsum[n - 1] - parsum[i]; if (abs(cursum2 - cursum1) < abs(sum2 - sum1)){ sum1 = cursum1; sum2 = cursum2; } } return {sum1, sum2}; } diamgr find_gr_dim(int ver){ if (v[ver].size() == 0){ diamgr infogr(ver, ver, 0, 0, 0); return infogr; } int s = Dijkstra(ver); int f = Dijkstra(s); memset(parsum, 0, sizeof(parsum)); int cntver = init_parsums(s, f, parsum); pair<int, int> sums = find_mindif(cntver, parsum); diamgr infogr(s, f, sums.first + sums.second, sums.first, sums.second); return infogr; } inline void subtask123(int *a, int *b, int *t){ init_vectors(a, b, t); diamgr info1, info2; for (int i = 0; i < n; ++i) if (!checkver[i]){ if (info1.s == -1) info1 = find_gr_dim(i); else info2 = find_gr_dim(i); } anscost = info1.cost; anscost = max(anscost, info2.cost); anscost = max(anscost, max(info1.sum1, info1.sum2) + max (info2.sum1, info2.sum2)); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n = N; m = M; lprice = L; //subtask1(A, B, T); subtask123(A, B, T); return anscost; }

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

dreaming.cpp: In function 'int init_parsums(int, int, int*)':
dreaming.cpp:93:18: warning: unused variable 'prev' [-Wunused-variable]
   93 |     int cur = f, prev = -1;
      |                  ^~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...