| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 42387 |
2018-02-26T15:38:56 Z |
dqhungdl |
버스 (JOI14_bus) |
C++14 |
|
392 ms |
10796 KB |
#include <bits/stdc++.h>
using namespace std;
struct data
{
int u,v,s,t;
};
typedef pair<int,int> ii;
data Edge[300005];
int n,m,T;
vector<ii> g[100005];
bool cmp(data x1,data x2)
{
return x1.t<x2.t;
}
int Binary(int u,int t)
{
int rs=-1,l=0,r=g[u].size()-1;
while(l<=r)
{
int mid=(l+r)/2;
if(g[u][mid].first<=t)
{
rs=g[u][mid].second;
l=mid+1;
}
else
r=mid-1;
}
return rs;
}
int main()
{
ios_base::sync_with_stdio(false);
//freopen("TEST.INP","r",stdin);
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>Edge[i].u>>Edge[i].v>>Edge[i].s>>Edge[i].t;
sort(Edge+1,Edge+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(Edge[i].u==1)
{
ii tmp=ii(Edge[i].t,Edge[i].s);
if(g[Edge[i].v].size()>0)
tmp.second=max(tmp.second,g[Edge[i].v].back().second);
g[Edge[i].v].push_back(tmp);
}
else
{
int t=Binary(Edge[i].u,Edge[i].s);
if(t!=-1)
{
ii tmp=ii(Edge[i].t,t);;
if(g[Edge[i].v].size()>0)
tmp.second=max(tmp.second,g[Edge[i].v].back().second);
g[Edge[i].v].push_back(tmp);
}
}
}
cin>>T;
int val;
while(T--)
{
cin>>val;
cout<<Binary(n,val)<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2836 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2836 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2836 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2836 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2840 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2888 KB |
Output is correct |
| 9 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 10 |
Correct |
3 ms |
3036 KB |
Output is correct |
| 11 |
Correct |
5 ms |
3036 KB |
Output is correct |
| 12 |
Correct |
4 ms |
3036 KB |
Output is correct |
| 13 |
Correct |
5 ms |
3036 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3036 KB |
Output is correct |
| 2 |
Correct |
157 ms |
3800 KB |
Output is correct |
| 3 |
Correct |
159 ms |
3900 KB |
Output is correct |
| 4 |
Correct |
19 ms |
3900 KB |
Output is correct |
| 5 |
Correct |
19 ms |
3900 KB |
Output is correct |
| 6 |
Correct |
27 ms |
3900 KB |
Output is correct |
| 7 |
Correct |
156 ms |
3900 KB |
Output is correct |
| 8 |
Correct |
4 ms |
3900 KB |
Output is correct |
| 9 |
Correct |
168 ms |
3900 KB |
Output is correct |
| 10 |
Correct |
163 ms |
3900 KB |
Output is correct |
| 11 |
Correct |
167 ms |
3900 KB |
Output is correct |
| 12 |
Correct |
162 ms |
4012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
7724 KB |
Output is correct |
| 2 |
Correct |
218 ms |
7724 KB |
Output is correct |
| 3 |
Correct |
221 ms |
7748 KB |
Output is correct |
| 4 |
Correct |
182 ms |
7768 KB |
Output is correct |
| 5 |
Correct |
186 ms |
7768 KB |
Output is correct |
| 6 |
Correct |
183 ms |
7928 KB |
Output is correct |
| 7 |
Correct |
220 ms |
8492 KB |
Output is correct |
| 8 |
Correct |
176 ms |
8876 KB |
Output is correct |
| 9 |
Correct |
188 ms |
8876 KB |
Output is correct |
| 10 |
Correct |
197 ms |
10128 KB |
Output is correct |
| 11 |
Correct |
218 ms |
10128 KB |
Output is correct |
| 12 |
Correct |
187 ms |
10128 KB |
Output is correct |
| 13 |
Correct |
212 ms |
10128 KB |
Output is correct |
| 14 |
Correct |
183 ms |
10128 KB |
Output is correct |
| 15 |
Correct |
191 ms |
10128 KB |
Output is correct |
| 16 |
Correct |
77 ms |
10128 KB |
Output is correct |
| 17 |
Correct |
68 ms |
10128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
325 ms |
10128 KB |
Output is correct |
| 2 |
Correct |
368 ms |
10128 KB |
Output is correct |
| 3 |
Correct |
364 ms |
10128 KB |
Output is correct |
| 4 |
Correct |
312 ms |
10128 KB |
Output is correct |
| 5 |
Correct |
370 ms |
10128 KB |
Output is correct |
| 6 |
Correct |
356 ms |
10128 KB |
Output is correct |
| 7 |
Correct |
345 ms |
10128 KB |
Output is correct |
| 8 |
Correct |
337 ms |
10128 KB |
Output is correct |
| 9 |
Correct |
336 ms |
10128 KB |
Output is correct |
| 10 |
Correct |
366 ms |
10796 KB |
Output is correct |
| 11 |
Correct |
373 ms |
10796 KB |
Output is correct |
| 12 |
Correct |
392 ms |
10796 KB |
Output is correct |
| 13 |
Correct |
358 ms |
10796 KB |
Output is correct |
| 14 |
Correct |
349 ms |
10796 KB |
Output is correct |
| 15 |
Correct |
355 ms |
10796 KB |
Output is correct |
| 16 |
Correct |
239 ms |
10796 KB |
Output is correct |
