oj.uz

답안 #42387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42387 2018-02-26T15:38:56 Z dqhungdl 버스 (JOI14_bus) C++14
100 / 100
 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";
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 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

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 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

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 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