| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P153PROD - ROUND 3D - Khôi phục hành trình |
Sau khi tìm được trạm đích của chuyến di dân, các trạm bắt tay vào xây dựng các không gian liên kết để di chuyển, liên kết giữa các trạm tạo thành một đồ thị dạng cây mà nút gốc chính là trạm đích cần di chuyển đến, người dân ở các trạm di chuyển từ nút lá lên các nút cha của nó dần dần lên nút gốc. Vì lý do an ninh nên hành trình của chuyến đi không được tiết lộ chi tiết mà chỉ tiết lộ trạm gần nhất mà hai trạm bất kì sẽ gặp nhau.
Cooper thấy khá hứng thú với hành trình này nên anh quyết định tìm cho ra bằng được. Các bạn hãy giúp anh ấy.
Input
Dòng đầu tiên chứa số tự nhiên n là số trạm (1 ≤ n ≤ 150).
n dòng sau, dòng thứ i chứa chứa n số nguyên, số thứ j - f[i][j] - chính là trạm gần nhất mà trạm i và trạm j sẽ gặp nhau. Đặc biệt f[i][j] = i nếu trạm j di chuyển trực tiếp đến trạm i và ngược lại, quy ước f[i][i] = i.
Output
Một dòng n số nguyên, số thứ i là nút cha của nút i, nếu nút i không có nút cha thì bằng 0.
Example
Input: 3
1 1 1
1 2 1
1 1 3 Output: 0 1 1
Test 2:
Input:
7
1 1 3 3 3 1 1
1 2 3 3 3 1 1
3 3 3 3 3 3 3
3 3 3 4 4 3 3
3 3 3 4 5 3 3
1 1 3 3 3 6 1
1 1 3 3 3 1 7
Output:
3 1 0 3 4 1 1
Hình vẽ minh họa test 2:
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-19 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2016-04-13 03:35:33
HD: http://mycodealgorithm.blogspot.com/2016/04/p153prod-round-3d-khoi-phuc-hanh-trinh.html |
