| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1026620 |
2024-07-18T08:43:02 Z |
김은성(#10945) |
COVID tests (CEOI24_covid) |
C++17 |
|
35 ms |
103184 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3fffffffffffffff;
int n, N;
ll L[1000009];
vector<pair<int, ll> > vec;
vector<pair<int, ll> > graph[4000009];
ll dist[4000009];
int tree[1<<21];
void update(int v, int l, int r, int idx, int val){
tree[v] = val;
if(l==r)
return;
int mid = (l+r)/2;
if(idx<=mid)
update(2*v, l, mid, idx, val);
else
update(2*v+1, mid+1, r, idx, val);
}
int possible(int v, int l, int r, int s, int e){
if(e<l || r<s)
return 0;
if(s<=l && r<=e)
return tree[v] != -1;
int mid = (l+r)/2;
return possible(2*v,l,mid,s,e) || possible(2*v+1,mid+1,r,s,e);
}
int lowerbound(int v, int l, int r, int e){ //e �̸� �� �ִ�
// printf("v=%d l=%d r=%d e=%d\n",v,l,r,e);
if(l==r)
return l<e ? tree[v] : -1;
int mid = (l+r)/2;
if(possible(2*v+1, mid+1, r, 1, e-1))
return lowerbound(2*v+1, mid+1, r, e);
return lowerbound(2*v, l, mid, e);
}
int upperbound(int v, int l, int r, int s){ //s �ʰ� �� �ִ�
if(l==r)
return l>s ? tree[v] : -1;
int mid = (l+r)/2;
if(possible(2*v, l, mid, s+1, n))
return upperbound(2*v, l, mid, s);
return upperbound(2*v+1, mid+1, r, s);
}
void dijkstra(int v){
int i, u;
for(i=0; i<N; i++)
dist[i] = INF;
dist[v] = 0;
priority_queue<pair<ll, int> > qa;
qa.push(make_pair(0, v));
while(!qa.empty()){
ll c = -qa.top().first;
v = qa.top().second;
printf("v=%d first=%d second=%d c=%lld\n", v, vec[v].first, vec[v].second, c);
qa.pop();
if(dist[v] != c)
continue;
for(i=0; i<graph[v].size(); i++){
u = graph[v][i].first;
ll tc = c + graph[v][i].second;
if(tc < dist[u]){
dist[u] = tc;
qa.push(make_pair(-tc, u));
}
}
// printf("done\n");
}
// printf("here\n");
}
int main(){
int i, j;
int sl, el, source, sink;
ll sc, ec;
vector<ll> temp;
scanf("%d", &n);
scanf("%d %lld", &sl, &sc);
scanf("%d %lld", &el, &ec);
temp.push_back(--sc);
temp.push_back(--ec);
for(i=1; i<=n; i++){
scanf("%lld", &L[i]);
temp.push_back(L[i]);
}
sort(temp.begin(), temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());
for(i=1; i<=n; i++){
if(i==sl || i==el){
for(j=0; j<temp.size(); j++){
if(temp[j] <= L[i]){
vec.push_back(make_pair(i, temp[j]));
}
}
}
else{
vec.push_back(make_pair(i, 0));
if(L[i])
vec.push_back(make_pair(i, L[i]));
}
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
N = vec.size();
vector<int> cons;
for(i=0; i<N; i++){
cons.push_back(i);
printf("l=%d c=%lld\n", vec[i].first, vec[i].second);
if(vec[i].first==sl && vec[i].second==sc)
source = i;
if(vec[i].first==el && vec[i].second==ec)
sink = i;
if(i==N-1)
break;
ll d = (vec[i].first==vec[i+1].first ? (vec[i+1].second-vec[i].second) : 1);
graph[i].push_back(make_pair(i+1, d));
graph[i+1].push_back(make_pair(i, d));
}
sort(cons.begin(), cons.end(), [](int &u, int &v){return make_pair(vec[u].second, vec[u].first) < make_pair(vec[v].second, vec[v].first);});
memset(tree, -1, sizeof(tree));
for(i=0; i<N; i++){
int v = cons[i];
int l = lowerbound(1, 1, n, vec[v].first), r = upperbound(1, 1, n, vec[v].first);
//printf("v=%d first=%d second=%d\n",v, vec[v].first, vec[v].second);
//printf("second=%d %d %d\n", vec[l].second, vec[r].second, vec[v].second);
//printf("v=%d lv=%d l=%d ll=%d r=%d lr=%d\n", v,vec[v].first,l,vec[l].first, r,vec[r].first);
if(l!=-1 && (L[vec[l].first] == vec[l].second || vec[l].second==vec[v].second)){
//printf("v=%d l=%d\n", v, l);
graph[v].push_back(make_pair(l, vec[v].first - vec[l].first));
graph[l].push_back(make_pair(v, vec[v].first - vec[l].first + vec[v].second-vec[l].second));
}
if(r!=-1 && (L[vec[r].first] == vec[r].second || vec[v].second==vec[r].second)){
//printf("v=%d r=%d\n", v, r);
graph[v].push_back(make_pair(r, vec[r].first-vec[v].first));
graph[r].push_back(make_pair(v, vec[r].first-vec[v].first + vec[v].second-vec[r].second));
}
update(1, 1, n, vec[v].first, v);
}
/*memset(tree, -1, sizeof(tree));
for(i=N-1; i>=0; i--){
int v = cons[i];
int l = lowerbound(1, 1, n, vec[v].first), r = upperbound(1, 1, n, vec[v].first);
//printf("v=%d lv=%d l=%d ll=%d r=%d lr=%d\n", v,vec[v].first,l,vec[l].first, r,vec[r].first);
if(l!=-1&& (L[vec[l].first] == vec[l].second || vec[v].second==vec[l].second)){
graph[l].push_back(make_pair(v, vec[v].first - vec[l].first));
if(vec[v].second == vec[l].second)
graph[v].push_back(make_pair(l, vec[v].first - vec[l].first));
}
if(r!=-1&& (L[vec[r].first] == vec[r].second || vec[v].second==vec[r].second)){
graph[r].push_back(make_pair(v, vec[r].first-vec[v].first));
if(vec[v].second == vec[r].second)
graph[v].push_back(make_pair(r, vec[r].first-vec[v].first));
}
update(1, 1, n, vec[v].first, v);
}*/
dijkstra(source);
ll mn = dist[sink];
for(i=0; i<N; i++){
}
printf("%lld\n", dist[sink]);
return 0;
}
Compilation message
Main.cpp: In function 'void dijkstra(int)':
Main.cpp:56:39: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
56 | printf("v=%d first=%d second=%d c=%lld\n", v, vec[v].first, vec[v].second, c);
| ~^
| |
| int
| %lld
Main.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(j=0; j<temp.size(); j++){
| ~^~~~~~~~~~~~
Main.cpp:157:8: warning: unused variable 'mn' [-Wunused-variable]
157 | ll mn = dist[sink];
| ^~
Main.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
Main.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d %lld", &sl, &sc);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d %lld", &el, &ec);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%lld", &L[i]);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:157:8: warning: 'sink' may be used uninitialized in this function [-Wmaybe-uninitialized]
157 | ll mn = dist[sink];
| ^~
Main.cpp:156:13: warning: 'source' may be used uninitialized in this function [-Wmaybe-uninitialized]
156 | dijkstra(source);
| ~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
102980 KB |
Protocol violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
102992 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
103184 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
