oj.uz

Submission #42363

# Submission time Handle Problem Language Result Execution time Memory
42363 2018-02-26T13:46:33 Z nickyrio 버스 (JOI14_bus) C++14
0 / 100
 267 ms 35244 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() {
  	IO;
    cin >> n >> m;
    REP(i, m) {
        cin >> g[i].a >> g[i].b >> g[i].x >> g[i].y;
        e[g[i].a].push_back(i);
    }
}
bool disabled[N];

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

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;
    cin >> q;
    REP(i, q) {
        int x;
        cin >> x;
        int pos = upper_bound(res.begin(), res.end(), pp(x + 1, -1)) - res.begin() - 1;
        if (pos < 0) cout << -1 << '\n';
        else cout << res[pos].second << '\n';
    }
}
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:69:5: note: in expansion of macro 'REP'
     REP(i, res.size()) if (i) {
     ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 20 ms 24032 KB Output is correct
3 Correct 20 ms 24032 KB Output is correct
4 Correct 23 ms 24032 KB Output is correct
5 Correct 20 ms 24036 KB Output is correct
6 Correct 20 ms 24052 KB Output is correct
7 Incorrect 20 ms 24056 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24112 KB Output is correct
2 Correct 43 ms 24924 KB Output is correct
3 Correct 43 ms 24924 KB Output is correct
4 Correct 23 ms 24924 KB Output is correct
5 Incorrect 22 ms 24924 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34292 KB Output is correct
2 Correct 198 ms 34292 KB Output is correct
3 Correct 204 ms 34292 KB Output is correct
4 Correct 205 ms 34320 KB Output is correct
5 Correct 193 ms 34320 KB Output is correct
6 Correct 209 ms 34832 KB Output is correct
7 Incorrect 180 ms 34832 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 34964 KB Output is correct
2 Correct 224 ms 34964 KB Output is correct
3 Correct 226 ms 35072 KB Output is correct
4 Correct 238 ms 35072 KB Output is correct
5 Correct 257 ms 35072 KB Output is correct
6 Correct 223 ms 35244 KB Output is correct
7 Incorrect 220 ms 35244 KB Output isn't correct
8 Halted 0 ms 0 KB -