| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 43222 |
2018-03-11T00:14:59 Z |
smu201111192 |
버스 (JOI14_bus) |
C++14 |
|
1000 ms |
92472 KB |
#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 100005;
const int MAXV = 1000005;
int n,m,id = 0;
namespace fio {
const int BSIZE = 1<<17;
unsigned char buffer[BSIZE];
unsigned char *p = buffer + BSIZE;
inline unsigned char readChar() {
if (p == buffer + BSIZE) {
fread(buffer, 1, 1 << 17, stdin);
p = buffer;
}
return *p++;
}
int readInt() {
unsigned char c = readChar();
while (c<'-')c = readChar();
int ret = 0;
do {
ret = ret * 10 + c - '0';
c = readChar();
} while (c >='-');
return ret;
}
}
//map<pair<int,int>,int> dict;
pair<int,int> cv[MAXV];
vector<int> adj[MAXV];
vector<int> node[MAXV];
struct edge{
int u,v,st,ed;
}e[MAXV];
int dp[MAXV];
void addEdge(int u,int v){
adj[v].push_back(u);
}
vector<pair<int,int> > dd;
int dict(pair<int,int> c){
return lower_bound(dd.begin(),dd.end(),c) - dd.begin() + 1;
}
int main(){
//ios::sync_with_stdio(false); cin.tie(0);
n =fio::readInt();
m = fio::readInt();
//cin >> n >> m;
for(int i = 1; i <= m; i++){
e[i].u = fio::readInt();
e[i].v = fio::readInt();
e[i].st = fio::readInt();
e[i].ed = fio::readInt();
//cin >> e[i].u >> e[i].v >> e[i].st >> e[i].ed;
dd.push_back({e[i].u,e[i].st});
dd.push_back({e[i].v,e[i].ed});
node[e[i].u].push_back(e[i].st);
node[e[i].v].push_back(e[i].ed);
}
for(int i = 1; i <= n; i++) {
sort(node[i].begin(),node[i].end());
node[i].erase(unique(node[i].begin(),node[i].end()),node[i].end());
}
vector<pair<int,int> > ord;
sort(dd.begin(),dd.end());
dd.erase(unique(dd.begin(),dd.end()),dd.end());
for(int i = 0; i < dd.size(); i++){
cv[i+1] = dd[i];
ord.push_back({dd[i].second,i+1});
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < (int)node[i].size() - 1; j++){
int tu = node[i][j];
int tv = node[i][j+1];
addEdge(dict(make_pair(i,tu)),dict(make_pair(i,tv)));
}
}
for(int i = 1; i <= m; i++){
int u = e[i].u; int v = e[i].v;
int st = e[i].st; int ed = e[i].ed;
addEdge(dict({u,st}),dict({v,ed}));
}
sort(ord.begin(),ord.end());
reverse(ord.begin(),ord.end());
memset(dp,0x3f3f3f3f,sizeof(dp));
vector<pair<int,int> > vc;
int iter = 0;
for(int i = 0; i<ord.size();i++){
int x = ord[i].second;
int tm = ord[i].first;
int pv = cv[x].first;
if(pv == 1) vc.push_back(make_pair(dp[x],tm));
if(pv == n)
dp[x] = tm;
for(auto y:adj[x]){
dp[y] = min(dp[y],dp[x]);
iter++;
}
}
//assert(iter < 2000000);
int Q;
//cin>> Q;
Q = fio::readInt();
sort(vc.begin(),vc.end());
for(int i = 1; i <= Q; i++){
int tm;
tm = fio::readInt();
//cin >> tm;
if(vc.size() == 0){
cout<<-1; continue;
}
int lo = 0;
int hi = vc.size()-1;
int ret = -1;
while(lo <= hi){
int mid = (lo+hi) / 2;
if(vc[mid].first <= tm){
lo = mid + 1;
ret = max(ret,vc[mid].second);
}
else hi = mid - 1;
}
printf("%d\n",ret);
//cout<<ret<<"\n";
}
return 0;
}
Compilation message
bus.cpp: In function 'int main()':
bus.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < dd.size(); i++){
^
bus.cpp:105:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<ord.size();i++){
^
bus.cpp: In function 'unsigned char fio::readChar()':
bus.cpp:30:45: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(buffer, 1, 1 << 17, stdin);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
51320 KB |
Output is correct |
| 2 |
Correct |
46 ms |
51320 KB |
Output is correct |
| 3 |
Correct |
47 ms |
51448 KB |
Output is correct |
| 4 |
Correct |
46 ms |
51448 KB |
Output is correct |
| 5 |
Correct |
46 ms |
51484 KB |
Output is correct |
| 6 |
Correct |
47 ms |
51492 KB |
Output is correct |
| 7 |
Correct |
47 ms |
51492 KB |
Output is correct |
| 8 |
Correct |
47 ms |
51552 KB |
Output is correct |
| 9 |
Correct |
55 ms |
51552 KB |
Output is correct |
| 10 |
Correct |
49 ms |
51552 KB |
Output is correct |
| 11 |
Correct |
46 ms |
51804 KB |
Output is correct |
| 12 |
Correct |
46 ms |
51820 KB |
Output is correct |
| 13 |
Correct |
46 ms |
51820 KB |
Output is correct |
| 14 |
Correct |
45 ms |
51820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
51820 KB |
Output is correct |
| 2 |
Correct |
58 ms |
52464 KB |
Output is correct |
| 3 |
Correct |
62 ms |
52476 KB |
Output is correct |
| 4 |
Correct |
47 ms |
52476 KB |
Output is correct |
| 5 |
Correct |
46 ms |
52476 KB |
Output is correct |
| 6 |
Correct |
46 ms |
52476 KB |
Output is correct |
| 7 |
Correct |
55 ms |
52476 KB |
Output is correct |
| 8 |
Correct |
54 ms |
52476 KB |
Output is correct |
| 9 |
Correct |
66 ms |
52476 KB |
Output is correct |
| 10 |
Correct |
67 ms |
52524 KB |
Output is correct |
| 11 |
Correct |
56 ms |
52524 KB |
Output is correct |
| 12 |
Correct |
63 ms |
52732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1014 ms |
91700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1002 ms |
92472 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
