oj.uz

Submission #42361

# Submission time Handle Problem Language Result Execution time Memory
42361 2018-02-26T13:39:29 Z nickyrio 버스 (JOI14_bus) C++14
35 / 100
 1000 ms 35504 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

using namespace std;

struct edge {
    int a, b, x, y;
}g[N];
vector<int> e[N];
int d[N], visited[N];
int n, m;

void Enter() {
    scanf("%d %d", &n, &m);
    REP(i, m) {
        scanf("%d %d %d %d", &g[i].a, &g[i].b, &g[i].x, &g[i].y);
        e[g[i].a].push_back(i);
    }
}

void dfs(int u, int isEdge, int MAX, int now) {
    if (isEdge) {
        visited[u] = true;
        d[u] = MAX;
        dfs(g[u].b, 0, MAX, now);
    }
    else {
        for (int id : e[u]) {
            if (visited[id] == false && g[id].x >= now) {
                dfs(id, 1, MAX, g[id].y);
            }
        }
    }
}

vector<pp> res;

void Process() {
    sort(e[1].begin(), e[1].end(), [] (const int &a, const int &b) {
         return g[a].x > g[b].x;
    });
    for (int id : e[1]) {
        if (visited[id] == false) {
            dfs(id, 1, g[id].x, g[id].y);
        }
    }
    REP(i, m) {
        if (g[i].b == n && visited[i]) {
            res.push_back(pp(g[i].y, d[i]));
        }
    }
    sort(res.begin(), res.end());
    REP(i, res.size()) if (i) {
        res[i].second = max(res[i].second, res[i - 1].second);
    }
}

void Query() {
    int q;
    scanf("%d", &q);
    REP(i, q) {
        int x;
        scanf("%d", &x);
        int pos = upper_bound(res.begin(), res.end(), pp(x + 1, -1)) - res.begin() - 1;
        if (pos < 0) printf("-1\n");
        else printf("%d\n", res[pos].second);
    }
}
int main() {
    Enter();
    Process();
    Query();
}

Compilation message

bus.cpp: In function 'void Process()':
bus.cpp:4:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i, a) for (int i = 0; i<a; ++i)
                                    ^
bus.cpp:64:5: note: in expansion of macro 'REP'
     REP(i, res.size()) if (i) {
     ^
bus.cpp: In function 'void Enter()':
bus.cpp:25:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
                           ^
bus.cpp:27:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &g[i].a, &g[i].b, &g[i].x, &g[i].y);
                                                                 ^
bus.cpp: In function 'void Query()':
bus.cpp:71:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
                    ^
bus.cpp:74:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 20 ms 23908 KB Output is correct
3 Correct 20 ms 23960 KB Output is correct
4 Correct 21 ms 24036 KB Output is correct
5 Correct 21 ms 24116 KB Output is correct
6 Correct 21 ms 24116 KB Output is correct
7 Correct 21 ms 24116 KB Output is correct
8 Correct 21 ms 24116 KB Output is correct
9 Correct 24 ms 24136 KB Output is correct
10 Correct 21 ms 24136 KB Output is correct
11 Correct 24 ms 24136 KB Output is correct
12 Correct 22 ms 24180 KB Output is correct
13 Correct 21 ms 24304 KB Output is correct
14 Correct 22 ms 24304 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24304 KB Output is correct
2 Correct 61 ms 24944 KB Output is correct
3 Correct 51 ms 24944 KB Output is correct
4 Correct 24 ms 24944 KB Output is correct
5 Correct 23 ms 24944 KB Output is correct
6 Correct 27 ms 24944 KB Output is correct
7 Correct 40 ms 24944 KB Output is correct
8 Correct 24 ms 24944 KB Output is correct
9 Correct 46 ms 24944 KB Output is correct
10 Correct 57 ms 24944 KB Output is correct
11 Correct 49 ms 24944 KB Output is correct
12 Correct 65 ms 25248 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 34224 KB Output is correct
2 Correct 296 ms 34268 KB Output is correct
3 Correct 276 ms 34268 KB Output is correct
4 Correct 314 ms 34268 KB Output is correct
5 Correct 273 ms 34268 KB Output is correct
6 Correct 297 ms 34672 KB Output is correct
7 Correct 231 ms 34672 KB Output is correct
8 Correct 327 ms 34692 KB Output is correct
9 Correct 291 ms 34792 KB Output is correct
10 Execution timed out 1076 ms 34792 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 34792 KB Output is correct
2 Correct 298 ms 34792 KB Output is correct
3 Correct 309 ms 34864 KB Output is correct
4 Correct 294 ms 35024 KB Output is correct
5 Correct 288 ms 35024 KB Output is correct
6 Correct 284 ms 35228 KB Output is correct
7 Correct 277 ms 35228 KB Output is correct
8 Correct 326 ms 35252 KB Output is correct
9 Correct 312 ms 35504 KB Output is correct
10 Execution timed out 1059 ms 35504 KB Time limit exceeded
11 Halted 0 ms 0 KB -