제출 #251227

#제출 시각아이디문제언어결과실행 시간메모리
251227AaronNaidu웜뱃 (IOI13_wombats)C++14
21 / 100
20014 ms33088 KiB
#include <bits/stdc++.h> #include "wombats.h" using namespace std; int r, c; int h[5000][200], v[5000][200]; int prefSums[5000]; int dists[1000000]; bool visited[1000000]; priority_queue<pair<int, int> > q; vector<pair<int, int> > graph[1000000]; void changeH(int p, int q, int w) { for (int i = 0; i < graph[c*p+q].size(); i++) { if (graph[c*p+q][i].first == c*p+q+1) { //cout << "Change H part 1:" << graph[c*p+q][i].second << "\n"; graph[c*p+q][i].second = w; //cout << "Changed to " << graph[c*p+q][i].second << "\n"; } } for (int i = 0; i < graph[c*p+q+1].size(); i++) { if (graph[c*p+q+1][i].first == c*p+q) { //cout << "Change H part 2:" << graph[c*p+q+1][i].second << "\n"; graph[c*p+q+1][i].second = w; //cout << "Changed to " << graph[c*p+q+1][i].second << "\n"; } } } void changeV(int p, int q, int w){ if (c == 1) { int diff = w - (prefSums[p+1] - prefSums[p]); for (int i = p+1; i < r; i++) { prefSums[i] += diff; } return; } for (int i = 0; i < graph[i*p+q].size(); i++) { if (graph[c*p+q][i].first == c*p+ c + q) { //cout << "Change V: " << graph[c*p+q][i].second << "\n"; graph[c*p+q][i].second = w; //cout << "Changed to " << graph[c*p+q][i].second << "\n"; } } } void init(int R, int C, int H[5000][200], int V[5000][200]) { r = R; c = C; for (int i = 0; i < r; i++) { for (int j = 0; j < c-1; j++) { graph[i * c + j].push_back({i*c+j+1, H[i][j]}); graph[i*c + j+1].push_back({i*c+j, H[i][j]}); //cout << "Constructing graph\n"; } } for (int i = 0; i < r-1; i++) { for (int j = 0; j < c; j++) { graph[i*c+j].push_back({i*c + c + j,V[i][j]}); //cout << "Constructing graph\n"; } } if (c == 1) { for (int i = 1; i < r; i++) { prefSums[i] = prefSums[i-1] + V[i-1][0]; } } } int escape(int v1, int v2) { if (c == 1) { return prefSums[r-1]; } int startNode = v1; int endNode = c*(r-1)+v2; //cout << "Going from " << startNode << " to " << endNode << "\n"; for (int i = 0; i < r * c; i++) { dists[i] = 1000000000; visited[i] = false; } q.push({0, startNode}); dists[startNode] = 0; while (!q.empty()) { //cout << "in BFS\n"; int dist = q.top().first; int node = q.top().second; //cout << "At node " << node << " at dist " << dist << "\n"; q.pop(); if (!visited[node]) { visited[node] = true; dists[node] = min(-dist, dists[node]); for (auto i : graph[node]) { if (!visited[i.first]) { q.push({dist-i.second, i.first}); //cout << "Pushing " << i.first << " at dist " << dist-i.second << "\n"; } } } } return dists[endNode]; }

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

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[c*p+q].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~~
wombats.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[c*p+q+1].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[i*p+q].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~~
#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...