제출 #43212

#제출 시각아이디문제언어결과실행 시간메모리
43212smu201111192버스 (JOI14_bus)C++14
35 / 100
327 ms86456 KiB
#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; map<pair<int,int>,int> dict; pair<int,int> cv[MAXV]; vector<int> adj[MAXV]; vector<int> node[MAXN]; struct edge{ int u,v,st,ed; void read(){cin>>u>>v>>st>>ed;} }e[MAXN]; int dp[MAXV]; void addEdge(int u,int v){ adj[u].push_back(v); } int go(int cur){ if(cv[cur].first == n) return cv[cur].second; if(dp[cur] != -1) return dp[cur]; dp[cur] = 2e9; for(auto &x : adj[cur]){ dp[cur] = min(dp[cur],go(x)); } return dp[cur]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; node[1].push_back(0); for(int i = 1; i <= m; i++){ e[i].read(); dict[make_pair(e[i].u,e[i].st)]; dict[make_pair(e[i].v,e[i].ed)]; assert(dict.size() < MAXV); 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()); } dict[make_pair(1,0)]; for(auto it = dict.begin(); it!= dict.end(); it++){ it->second = ++id; cv[id] = it->first; } assert(id<MAXV); 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; adj[dict[make_pair(u,st)]].push_back(dict[make_pair(v,ed)]); } memset(dp,-1,sizeof(dp)); int q; cin >> q; for(int i = 1;i <= q; i++){ int goal; cin >> goal; int low = 0; int high = node[1].size()-1; int ans = -1; while(low <= high){ int mid = (low+high)/2; int id = dict[make_pair(1,node[1][mid])]; if(go(id) <= goal){ ans = max(ans,node[1][mid]); low = mid + 1; } else high = mid - 1; } cout<<ans<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...