| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 620799 |
2022-08-03T09:23:00 Z |
조영욱(#8520) |
Railway Trip (JOI17_railway_trip) |
C++17 |
|
2000 ms |
24780 KB |
#include <bits/stdc++.h>
using namespace std;
int n,k,q;
int lev[100001];
const int INF=1e9;
vector<int> vec[100001];
typedef pair<int,int> P;
vector<P> adj[100001];
int dist[100001];
bool vis[100001];
struct Fenwick {
int arr[100001];
int psum[100001];
int sum(int i) {
return psum[i];
}
void update(int i,int val) {
arr[i]+=val;
}
void cal() {
for(int i=1;i<=n;i++) {
psum[i]=psum[i-1]+arr[i];
}
}
};
Fenwick ft[21];
void dijk(int st) {
priority_queue<P,vector<P>,greater<P>> pq;
pq.push(P(0,st));
dist[st]=0;
while (!pq.empty()) {
int now=pq.top().second;
pq.pop();
if (vis[now]) {
continue;
}
vis[now]=true;
for(int i=0;i<adj[now].size();i++) {
int nt=adj[now][i].first;
if (dist[nt]>dist[now]+adj[now][i].second) {
dist[nt]=dist[now]+adj[now][i].second;
pq.push(P(dist[nt],nt));
}
}
}
}
int down(int ind,int x) {
auto iter=upper_bound(vec[ind].begin(),vec[ind].end(),x);
if (iter!=vec[ind].begin()) {
iter--;
return (*iter);
}
else {
return -1;
}
}
int up(int ind,int x) {
auto iter=lower_bound(vec[ind].begin(),vec[ind].end(),x);
return (iter==vec[ind].end())?-1:(*iter);
}
set<int> s;
vector<int> save;
void connect(int x,int i) {
auto iter=s.lower_bound(x);
if (next(iter)!=s.end()) {
iter++;
int now=(*iter);
int d=ft[i].sum(now)-ft[i].sum(x);
adj[now].push_back(P(x,d));
adj[x].push_back(P(now,d));
save.push_back(now);
save.push_back(x);
//printf("%d %d %d %d\n",i,now,x,d);
iter--;
}
if (iter!=s.begin()) {
iter--;
int now=(*iter);
int d=ft[i].sum(x)-ft[i].sum(now);
adj[now].push_back(P(x,d));
adj[x].push_back(P(now,d));
//printf("%d %d %d %d\n",i,now,x,d);
save.push_back(now);
save.push_back(x);
}
}
int main(void ) {
scanf("%d %d %d",&n,&k,&q);
for(int i=1;i<=n;i++) {
dist[i]=INF;
scanf("%d",&lev[i]);
vec[lev[i]].push_back(i);
for(int j=1;j<=lev[i];j++) {
ft[j].update(i,1);
}
}
for(int i=1;i<=k;i++) {
ft[i].cal();
}
for(int ind=0;ind<q;ind++) {
int a,b;
scanf("%d %d",&a,&b);
if (a>b) {
swap(a,b);
}
s.clear();
save.clear();
for(int i=k;i>0;i--) {
int al=down(i,a);
int ar=up(i,a);
int bl=down(i,b);
int br=up(i,b);
if (al!=-1)
s.insert(al);
if (ar!=-1)
s.insert(ar);
if (bl!=-1)
s.insert(bl);
if (br!=-1)
s.insert(br);
if (al!=-1) {
connect(al,i);
}
if (ar!=-1&&al!=ar) {
connect(ar,i);
}
if (bl!=-1) {
connect(bl,i);
}
if (br!=-1&&bl!=br) {
connect(br,i);
}
}
dijk(a);
printf("%d\n",dist[b]-1);
for(int j=0;j<save.size();j++) {
if (save[j]==-1) continue;
adj[save[j]].clear();
dist[save[j]]=INF;
vis[save[j]]=false;
}
}
}
Compilation message
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d %d %d",&n,&k,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%d",&lev[i]);
| ~~~~~^~~~~~~~~~~~~~
railway_trip.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%d %d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
10068 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
10124 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2053 ms |
24780 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
10068 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
