oj.uz

답안 #115341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115341 2019-06-06T17:42:07 Z model_code Traffic (CEOI11_tra) C++17
32 / 100
 5000 ms 41936 KB 
/* Slower solution of TRA/jlac012
 * A bin-search solution.
 * Author: Tomasz Kociumaka, reusing some code by Mateusz Baranowski
 *
 */

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define pb push_back
#define MAXN 300001

typedef pair<int, int> PII;

int n, m, A, B;
int i, l;
int tmp1, tmp2;
vector<PII> west, east; /* junctions on west riverbank */
vector<int> edges[MAXN], revedges[MAXN]; /* junctions in road network */
int eastern[MAXN]; /* equals 1 when junction lies on the east bank */
size_t visited[MAXN];
bool any[MAXN];

void read_input() {
  scanf ("%d %d %d %d", &n, &m, &A, &B);
  for (i = 1; i <= n; ++i) {
    scanf ("%d %d", &tmp1, &tmp2);
    eastern[i] = 0;
    if (tmp1 == 0) west.pb(make_pair(tmp2, i));
    else if (tmp1 == A) {
        east.pb(make_pair(tmp2, i));
        eastern[i] = 1;
    }
  }
  sort(west.begin(), west.end());
  sort(east.begin(), east.end());
  for (size_t s = 0; s < east.size(); ++s) {
      eastern[east[s].second] = s+1;
  }
  while (m-->0) {
    scanf ("%d %d %d", &tmp1, &tmp2, &i);
    edges[tmp1].pb(tmp2);
    revedges[tmp2].pb(tmp1);
    if (i == 2) {
        edges[tmp2].pb(tmp1);
        revedges[tmp1].pb(tmp2);
    }
  }
}

pair<int, int> reachable(int v, size_t s) {
    size_t j;
    int result = 0;
    int mx = 0;
    queue<int> q;
    q.push(v);
    while (!q.empty()) {
        i = q.front(); q.pop();
        result += (eastern[i] != 0);
        mx = max(eastern[i], mx);
        for (j = 0; j < edges[i].size(); ++j) {
            l = edges[i][j];
            if (visited[l] != s) { visited[l] = s; q.push(l); }
        }
    }
    return make_pair(result, mx);
}

void generate_output() {
    for (i = 1; i <= n; ++i) visited[i] = 0;
    queue<int> Q;
    for (i = 0; i < (int) east.size(); ++i) {
        Q.push(east[i].second);
        visited[east[i].second] = 1;
    }
    while (!Q.empty()) {
        i = Q.front(); Q.pop();
    //    printf("in %d\n", i);
        for (size_t j = 0; j < revedges[i].size(); ++j) {
            l = revedges[i][j];
            if (visited[l] != 1) { visited[l] = 1; Q.push(l); }
        }
    }
    for (i = 0; i < (int) west.size(); ++i) {
        any[i] = (visited[west[i].second] == 1);
     //   printf("%d: %d\n", i, any[i]);
    }

    for (i = 1; i <= n; ++i) visited[i] = 0;
    int s = (int) west.size();
    PII cur,  prev = make_pair(-1, -1);
    int delta = 1;
    int ph = 0;
    while(true) {
        ++ph;
       
        if (s-delta>=0) {
            if (!any[s-delta]) --delta;
            if (delta == 0) {
                printf("0\n");
                delta = 1;
                --s;
                continue;
            }
         //   printf("%d %d\n", s, delta);
            cur = reachable(west[s-delta].second, ph);
            if (cur == prev) {
                for (i=0; i<delta; ++i) printf("%d\n",(any[s-i-1])?cur.first:0);
                s -= delta;
                delta *= 2;
            } else {
                if (delta > 1) delta /= 2;
                else {
                    printf("%d\n", cur.first);
                    prev = cur;
                    --s;
                }
            }
        } else if (delta > 1){
            delta /= 2;
        } else break;
    }
}

int main() {
    read_input();
    generate_output();
    return 0;
}

Compilation message

tra.cpp: In function 'void read_input()':
tra.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d %d", &n, &m, &A, &B);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:30:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &tmp1, &tmp2);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:44:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &tmp1, &tmp2, &i);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 12 ms 14464 KB Output is correct
4 Correct 14 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 14 ms 14464 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 14 ms 14484 KB Output is correct
3 Correct 14 ms 14464 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 14668 KB Output is correct
2 Correct 84 ms 14908 KB Output is correct
3 Correct 17 ms 14720 KB Output is correct

Subtask #5
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 15360 KB Output is correct
2 Execution timed out 5030 ms 17900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 17144 KB Output is correct
2 Execution timed out 5038 ms 18972 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 19492 KB Output is correct
2 Execution timed out 5086 ms 21200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 21212 KB Output is correct
2 Execution timed out 5076 ms 21544 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 24596 KB Output is correct
2 Execution timed out 5105 ms 26476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 461 ms 30200 KB Output is correct
2 Execution timed out 5012 ms 33712 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1261 ms 41936 KB Output is correct
2 Execution timed out 5021 ms 34892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 24256 KB Output is correct
2 Execution timed out 5056 ms 36044 KB Time limit exceeded
3 Halted 0 ms 0 KB -