| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P156SUMA - ROUND 6A - Tặng quà |
#S là một nhân vật huyền thoại chi phối toàn bộ các thế lực trong kì TI năm nay. Sau khi sử dụng aura của mình để kiếm được một khoản kha khá, anh muốn tặng một phần nhỏ cho 2 người trong số n người trong một group trên facebook.
Luật được #S đưa ra khách quan như sau: người thứ i sẽ tiến cử 2 người xi và yi là người may mắn (người đó không được chỉ chính mình). Riêng #S sẽ chọn ra 2 người A, B để tặng quà. Một lựa chọn (A, B) được coi là thỏa mãn nếu như có ít nhất p người đồng ý. Người M đồng ý với sự lựa chọn (A, B) nếu như ít nhất một trong 2 người mà người đó tiến cử chính là A hoặc B. Bạn cần tính xem có bao nhiêu cách lựa chọn ra 2 người may mắn?
Lưu ý: sự (A, B) và (B, A) chỉ được tính là một. Đặc biệt, nếu M == A (hoặc M == B), người M sẽ đồng ý với lựa chọn của #S nếu như trong danh sách tiến cử của M có người B (hoặc có A).
Input
Dòng đầu tiên chứa 2 số n và p (3 <= n <= 3*10^5; 0 <= p <= n).
N dòng sau, mỗi dòng chứa 2 số xi và yi (1 <= xi, yi <= n; xi != i ; yi != i; xi != yi).
Output
In ra số cách chọn của #S.
Example
Test 1:
Input:
3 2
2 3
3 1
2 1
Output:
3
Test 2:
Input:
4 2
2 3
1 4
1 4
2 1
Output:
6
Giải thích test 2: Các cặp (A, B) thỏa mãn là (1, 2); (1, 3); (1, 4); (2, 3); (2,4); (3, 4).
Test 3:
8 6
5 6
5 7
5 8
6 2
2 1
7 3
1 3
1 4
Output:
1
Giải thích test 3: Có 1 cách lựa chọn duy nhất đó là cặp (1, 5).
| Được gửi lên bởi: | adm |
| Ngày: | 2015-08-06 |
| 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
|
2015-09-03 15:44:25 UnKnown
có ai giải thích dùm mình chổ lưu ý được không. khó hiều quả |
|
|
2015-08-14 08:51:34 Nguyễn Trung Hiếu
ai cho mình xin bộ test dc ko nhỉ. ko biết sai chỗ nào nữa :( Last edit: 2015-08-14 17:45:57 |
