QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #645087 | #7860. Graph of Maximum Degree 3 | CanShangya | WA | 0ms | 3616kb | C++14 | 13.7kb | 2024-10-16 16:50:51 | 2024-10-16 16:50:53 |
Judging History
answer
// ⠉⠆⡁⠎⠡⠈⠆⠡⠈⡀⠀⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠀⠀
// ⠌⠠⠀⠄⠁⡀⠂⠐⠀⠠⠀⠠⠐⠀⠠⠐⠀⠄⠐⠀⠐⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠐⠀⠂⠐⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠐⠀⠂⠐⠀⠠⠐⠀⠠⠐⠀⠠⠈⠀
// ⠈⡐⠀⠈⠀⠀⠁⠈⠀⠀⠀⢀⠀⠀⠀⠀⢀⠀⠠⠀⠂⠀⠀⠀⢀⠀⠀⢀⠀⠀⢀⠀⠀⠀⠂⠀⠀⠄⠀⠀⠀⢀⠀⠀⢀⠀⠀⠀⠄⠀⠀⠂⠀⠀⡀⠀⠀⠀⢀⠀⠀⢀⠀⠄⠀
// ⠐⠠⠀⠅⡈⠄⠨⡐⠀⠂⠐⠀⠀⠂⠁⠀⠀⡀⢀⠀⠀⠂⠐⠀⠀⠀⠂⠀⠀⠂⠀⠀⠂⠐⠀⠂⠀⠀⠂⠐⠀⠀⠀⠂⠀⠀⠂⠀⠀⠂⠐⠀⠂⠀⠀⠐⠈⠀⠀⠀⠂⠀⠐⠀⠀
// ⠈⡀⠁⠠⠀⠀⠁⢀⠠⠐⠀⠀⠂⠀⠄⠈⠀⠀⢀⠀⠐⠀⠀⠐⠀⠠⠀⠐⠀⠠⠀⠁⢀⠀⠄⠀⠂⠁⠀⠀⠐⠀⠂⠀⠐⠀⠠⠀⠁⠠⠀⠄⠀⠂⠁⠀⠀⡀⠁⠀⠠⠐⠀⠂⠀
// ⠀⡀⠠⠀⠄⠀⠂⠀⠀⢀⠀⠠⠀⠄⠀⠠⠀⠂⢀⠀⠄⠐⠈⠀⠠⠀⡀⠄⠠⠀⠀⠄⠀⡀⠀⠐⠀⡀⠐⠈⠀⠄⠠⠐⠀⠠⠀⠀⠄⢀⠀⠄⠐⠀⡀⠐⠀⡀⠄⠈⠀⢀⠀⠀⠀
// ⠐⠀⠀⠄⠂⠀⠀⠂⠀⠂⠀⠄⢀⠠⠀⠄⠠⠀⢀⠀⠄⠠⠀⠄⠠⠀⢀⠀⠄⠠⠀⠄⢀⠀⠄⠈⠀⢀⠠⠀⠄⠠⠀⢀⠠⠀⠄⠂⠀⠠⠀⠀⠄⠀⡀⠠⠀⢀⠀⠄⠈⠀⡀⠀⠀
// ⠀⠌⠀⠠⠀⢈⠀⢀⠀⠌⠀⠄⠀⠀⠀⠀⠀⠄⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠀⠠⠀⠀⠠⠀⠀⠐⠀⠀⠀⠄⠀⠀⠄⠀⠀⠄⠀⠀⠂⠀⠐⠀⠠⠀⠀⠀⠄⠀⠀⠀⠂⠀⠀⠀⠀
// ⢀⠂⠀⠁⠠⠀⠀⡀⠠⠀⠈⠀⠀⠀⠁⠈⠀⠀⠈⠀⠁⠈⠀⠀⠁⠀⠁⠀⠂⠁⠀⠁⢀⠀⠁⡀⠈⠀⡀⠂⠐⠈⠀⠐⠀⠀⡈⠀⡀⠁⠀⠂⢀⠀⠁⠀⠂⠐⠈⠀⠐⠈⠀⠀⠀
// ⠀⡄⠂⠈⠀⢠⠁⠀⠀⠐⠀⠁⠀⡄⠂⠀⠀⡄⢠⠀⠀⢠⠀⠁⠀⢠⠀⢠⠀⡄⠀⠁⠀⠀⡄⠀⠀⠁⠀⠀⡄⢠⠀⡄⠀⠁⠀⠀⠀⠀⠁⠀⠀⠀⠈⠀⢠⠀⢠⠀⡄⠀⠁⠀⠀
// ⠐⠀⠀⠂⠐⠀⠀⠠⠐⠀⠀⠄⠀⠀⠀⠠⠀⠀⠀⠀⠄⠀⠀⡀⠄⠀⠀⠀⡀⢀⠠⠀⠈⠀⡀⠀⠁⡀⠠⠁⠀⠀⡀⢀⠠⠀⠈⠀⠄⠈⠀⡈⠀⠁⡀⠈⠀⢀⠀⡀⢀⠠⠀⠀⠀
// ⠐⠈⠀⡀⠐⠈⠀⠀⠀⠐⠀⠀⠄⠂⠀⠀⢠⡀⠀⠀⡀⠠⠀⠀⠀⠀⠄⠂⠀⠀⠀⠄⠂⠀⠄⠐⠀⠀⠀⠄⠂⠀⠀⠀⠀⠄⠂⠀⠄⠂⠀⠀⠐⠀⠀⠐⠀⠀⠀⠀⠀⠀⠄⠐⠀
// ⠀⠀⠄⠀⢈⠀⠀⠀⠂⠈⠀⢀⠀⠀⡀⢨⣿⣷⡀⠀⠀⡀⠀⠂⠀⠈⠀⢀⠀⠁⢀⠀⠐⠀⡀⠐⠈⠀⠐⠀⠀⠈⠀⠁⢀⠀⠐⠀⠀⠐⠈⠀⠐⠈⠀⠐⠈⠀⠁⠀⠁⡀⠀⠀⠀
// ⠀⠠⠀⠂⠀⠠⠀⠀⠀⠀⠌⠀⠀⠀⣽⣿⣿⣿⡇⠀⠀⠀⠀⡀⠄⠀⠁⠀⢀⠈⠀⡀⠈⠀⡀⠠⠀⠁⢀⠂⠁⠈⠀⠈⠀⡀⠄⠈⠀⡐⠀⠁⠠⠀⠁⢀⠀⠁⠈⠀⠁⢀⠀⠐⠀
// ⠀⠀⠐⠀⠀⠁⠀⠀⠁⠀⠀⠀⠶⣼⣿⣿⣿⣿⡇⠀⠀⠠⠀⠀⠀⠀⠄⠠⠀⠠⠀⠀⠄⠀⠄⠀⠀⠂⠀⡀⠄⠀⠁⠠⠀⠀⠠⠀⠁⠀⠠⠀⠄⠀⠌⠀⠀⠈⠀⠄⠈⠀⠀⠀⠀
// ⠀⠀⢈⠀⠈⠀⠀⠀⠈⠀⢀⠀⣾⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⡀⠐⠀⠠⠀⠀⠠⠐⠀⠀⠂⠀⠐⠀⠂⠀⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠂⠀⠄⠀⠂⠀⠐⠀⠁⠀⠄⠂⠐⠀⠠⠀
// ⠀⠀⠠⠀⠠⠀⠀⠐⠀⠐⠈⣿⣿⣿⣿⣿⣿⣿⠀⠀⡀⠁⠀⠀⠀⠀⡀⠀⠀⠁⢀⠀⠁⠀⠁⢀⠂⠀⠁⢀⠀⠀⠂⠀⠀⠂⢀⠀⡀⠐⠀⡀⠐⠀⠁⠀⠂⠁⢀⠀⡀⠀⠂⠀⠀
// ⠀⠀⠀⠄⠀⠀⠀⠀⠂⢀⣸⣿⣿⣿⣿⣿⣿⣿⠀⠀⢀⠠⠀⠀⠄⠀⠀⠀⠠⠈⠀⠀⢈⠀⠈⠀⠀⠄⠈⠀⢀⠠⠁⠈⠀⡀⠀⠀⡀⠠⠀⢀⠠⠀⠈⢀⠀⠄⠀⡀⠀⠠⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠈⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⡇⢀⠀⢀⠀⠀⠀⠠⠐⠀⠀⠀⠄⠐⠀⠀⠀⠂⠐⠀⠠⠐⠀⠀⠀⠀⠄⠐⠀⠠⠐⠀⠀⠀⠄⠀⠀⠂⠀⠀⠠⠀⠀⠠⠀⠄⠐⠀
// ⠀⠀⠠⠀⠈⠀⠀⠁⡄⣿⣿⣿⣿⣿⡿⠿⣿⡇⠀⠀⡀⠀⠈⠀⠀⢀⠀⠁⠀⡐⠀⠂⠁⠀⠂⢀⠈⠀⡀⠀⠁⠈⢀⠀⠀⠂⠀⢀⠀⠁⢀⠂⠈⠀⠐⠈⠀⡀⠐⠈⠀⢀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠠⠀⢰⣼⣿⣿⡿⢛⠡⡐⢂⣿⠁⠀⠀⠀⠠⠀⠀⠁⡀⠀⠄⠀⡀⠠⠀⢈⠀⠄⠀⠠⠀⢀⠀⠁⠠⠀⢀⠈⠀⢈⠀⠀⢈⠀⠀⡀⠁⡀⠄⠁⠀⠠⠀⠈⠀⡀⠠⠀
// ⠀⠀⠀⠀⠐⠀⣀⢰⣿⡿⠋⡔⢁⠢⢁⢾⡟⠀⠀⠀⠄⠀⡀⠄⠀⠀⠄⠠⠀⢀⠠⠀⠀⠀⠄⠐⠀⠠⠀⠀⠂⠀⠄⠀⠠⠀⢀⠠⠀⠂⠀⠄⠀⠄⠀⠀⠄⠂⠀⠄⠂⠀⠀⠀⠀
// ⠀⠀⠀⠀⠠⠀⠀⣾⠏⠶⠁⡔⡈⢢⠁⣾⡏⠀⠀⠂⠀⠀⠀⠀⠐⠀⠀⢀⠀⠀⠀⠀⠈⠀⠠⠐⠀⠠⠐⠀⠐⠀⠀⠂⠀⠄⠂⠀⠀⠐⠀⠀⠠⠀⠂⠀⠀⠐⠀⠀⠐⠀⠁⠀⠀
// ⠀⠀⠀⠀⠐⠂⢦⣿⢈⣛⠰⣀⠱⢀⢛⣽⠇⠀⠐⠀⠀⠁⠀⠁⠀⠀⠁⠀⠀⠁⠈⠀⠁⠀⡁⠀⠀⠄⠀⠂⠀⢈⠀⠐⠀⠀⠠⠀⠁⡀⠈⠀⠠⠀⠐⠈⠀⡀⠈⠀⡀⠈⠀⡀⠀
// ⠀⠀⠀⠄⠈⡁⣼⡯⠠⣿⠠⠐⣂⠡⢺⣿⢈⠀⠀⠀⠀⠠⠀⠐⠀⠀⠄⠠⠀⠈⠀⠀⠈⠀⡀⠐⠀⠠⠐⠀⠁⠀⠀⠄⠀⠁⠀⠠⠀⠀⠀⠁⠀⠠⠐⠀⠀⠀⠄⠂⠀⠠⠀⠀⠀
// ⠀⠀⠀⠀⠀⢔⣿⡧⠑⠦⢂⠱⠠⡘⣼⡇⠀⠀⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠂⠀⠀⢀⠀⠐⠀⠀⡀⠈⠀⠀⠀⠀⠂⠀⠀⠀⠐⠀⠁⢀⠀⠀⠀⠁⠀⠀⠀⢀⠀⠀⠐⠀
// ⠀⠀⠀⠁⠀⣺⣿⡗⡁⢛⠠⡁⠆⣱⣿⠀⠀⠂⠀⠐⠀⡀⠄⠂⠁⠀⠀⠁⠀⠀⠀⡀⠈⠀⡀⠀⠀⠂⠀⠀⠀⠐⠈⠀⡀⠄⠀⠁⠀⢀⠀⠀⠀⠀⠀⠁⠀⠀⠁⠀⠀⠀⠀⢀⠀
// ⠀⠀⠀⠀⠀⣼⡿⣏⠐⡡⠂⠥⣈⢳⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠐⠀⠁⢀⠀⠀⠀⡀⠠⠀⠀⠈⠀⠀⠄⠀⡀⠀⠀⡀⠈⠀⠀⠀⠐⠈⠀⠐⠀⠀⠂⠀⠂⠀⠄⠂⠀⠀
// ⠀⠀⠀⠀⠀⢸⣿⡇⡘⢠⠑⢂⠤⣿⣇⣤⣤⣤⣦⣥⣤⣤⣤⣤⣤⣄⣀⣀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠄⠠⠐⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⢀⠀⡀⠀⢀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⢸⣿⡇⠱⡈⠔⡨⣴⣿⠛⠩⡉⢍⠩⡉⢍⡙⡙⢋⡙⢛⠻⠿⣦⣤⣄⡀⠀⠀⠀⠠⠐⠀⠀⠀⠀⠀⠀⣀⣀⣀⣠⣄⣦⣴⣤⣤⣴⣴⣾⣶⢾⡶⢷⣶⣾⣶⣤⣤⣦
// ⠀⠀⡀⠁⠀⠈⣿⣯⠐⡄⢃⠴⠟⠣⠌⡡⢐⠊⡰⠁⢆⠰⢈⠔⡰⠈⡔⢂⠤⢉⡉⢛⠷⣦⣤⡀⠀⢀⣤⣤⣴⡶⠿⠟⡛⠋⡍⡉⠥⡈⠔⡰⢀⠆⠤⠐⣂⠐⢢⣰⣿⣿⣿⣿⣿
// ⠀⠀⠀⠀⠀⢢⣿⣿⡶⠈⡔⢠⠊⡁⢆⠡⢌⢂⠱⡈⠆⡱⠈⡔⠠⢃⠜⠠⠒⠤⡘⠄⡊⠤⠙⢻⣾⣟⠋⢌⡐⠄⢃⠢⡁⠎⡐⠄⣃⠘⡰⠐⡨⠐⡌⢡⠐⣼⣾⣿⣿⣿⣿⣿⣿
// ⠀⠀⠀⠀⢠⣿⣋⢙⠣⣁⠒⡠⠑⡨⠄⢊⠄⡊⠔⡠⢃⠔⢡⢂⠱⡈⢆⠡⡉⠔⡠⠃⠜⡠⢉⠤⡈⠿⣾⡠⠐⡌⢂⠅⠢⢑⡈⢒⡀⠣⡐⢡⠂⠱⠐⣦⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⠀⠀⠀⢀⣿⠇⠴⡈⠰⡀⠆⡁⠎⡐⠌⢢⠘⠄⢣⠐⡡⢊⠔⡈⢆⡑⠢⡑⡈⢆⠱⢈⠆⡑⠢⡐⠤⠡⠹⣿⣥⢶⣬⢖⡳⣖⡞⣖⢾⣱⣾⣶⣿⣾⣿⣿⣿⡿⠿⠿⠛⠛⠋⠉⠛
// ⠀⠀⢀⣸⡟⡸⢇⠰⢁⠢⢑⠨⡐⢡⠘⢄⠃⠎⡄⠣⡐⠡⢌⡐⢢⠈⡅⢢⠑⡂⠜⡠⢊⡐⠡⠒⡈⢅⠊⣽⣿⠛⠿⠿⠛⠛⠛⠛⠛⠛⠋⠛⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⢠⣿⢃⡍⢫⠐⣡⣾⣶⡷⢶⣧⣌⠢⠘⡥⠘⠤⣁⠃⢆⡘⢄⠃⡌⢂⠆⠱⡈⠤⢡⠐⡡⠃⢌⠰⢈⠴⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠀⠄⠈⠀
// ⠀⠀⣾⡏⠦⡐⢡⢺⣿⣿⣯⡀⢀⣿⣿⢠⠃⢄⢃⠒⡄⢩⠐⢌⠂⡱⠈⠆⡌⠱⣀⠣⠄⢃⠔⡉⢄⠊⡄⢚⣿⡇⠀⠠⠀⠀⠂⠀⠄⠠⠀⠀⠐⠀⠀⠂⠀⠐⠀⠀⠄⠂⠀⠠⠀
// ⠀⣾⡟⠰⢠⠑⠢⢸⣿⣿⣿⣿⣿⣿⡿⠰⣈⠢⠌⠰⡈⢆⡘⠄⢣⠐⣉⠒⡈⠅⡄⢢⢉⡄⢊⡔⠈⡔⠨⢰⣿⡇⠀⠀⠁⠀⠂⠁⠀⠀⠀⠁⠀⠀⠁⠀⠀⠂⠐⠀⠀⡀⠄⠂⠀
// ⣼⣿⣷⣷⣦⣇⡑⠢⢘⢻⠿⣿⡿⠛⢄⠃⡄⢒⠨⡁⠔⢂⠤⣉⠂⠥⣈⢂⠱⢈⣴⣾⠾⠿⢿⣶⡁⢢⠑⢺⣿⠁⠀⠈⠀⠀⡀⠐⠀⡁⠀⠁⡈⠀⠄⠈⠀⠀⠀⠈⠀⠀⠀⠀⠀
// ⣿⣿⡿⣟⣿⣿⣷⣅⠊⡄⢒⠠⢡⠉⡄⢊⠰⢈⠡⡘⢈⠆⡰⣿⣷⠆⡰⠀⢎⢰⣿⣿⣦⣥⣾⣿⣷⠀⢎⣹⡇⢉⠀⠀⠠⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠄⠀⠐⠀⠄⠀⠀
// ⣿⡿⣽⣿⣳⡿⣿⣿⡐⠌⡄⢃⢂⡑⢿⣦⣁⣊⠤⢑⣈⣔⣠⣙⠣⠐⠤⢉⠄⠚⢟⣿⣿⣿⣿⣿⢏⠌⢢⣿⠁⠀⠀⠀⠀⠀⠠⠀⠀⠀⠐⠀⠐⠀⠀⠐⠀⠀⠀⠂⠀⠀⠄⠀⠀
// ⣿⣿⢯⣿⣽⣿⣿⣿⠁⢎⡐⠌⡄⠒⡠⢹⣿⣿⣿⣿⣿⣿⣿⣿⣷⣍⡰⠈⡌⡘⢠⢊⡙⠻⡙⠋⡄⢊⣼⡟⠀⠀⠀⠀⠀⠁⠀⠀⡀⠈⠀⡀⠀⠀⠁⠀⢀⠀⢀⠀⠁⢀⠀⠀⠀
// ⢻⣿⣿⣳⣿⣿⣿⠏⢨⠐⡄⢊⠄⢣⠐⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣷⣶⠂⠰⡁⠔⠡⢂⣥⣾⡇⠀⠈⠀⠀⠈⠀⠈⠀⠀⠀⠀⠀⠠⠀⠀⠠⠀⠀⠀⠀⡀⠀⠀⠀⠀
// ⠠⢻⣿⠟⠟⡛⠡⣈⢂⠱⢈⠂⡜⠠⡑⢼⣿⣟⣿⣻⣟⡿⣿⣿⣿⣿⣿⣿⠍⡐⠤⡈⠥⠐⣉⣴⣿⣿⣿⣿⠀⣀⣀⣀⣤⣤⣤⣀⣠⣿⣤⠀⠀⠀⠠⠀⠀⠀⠂⠀⠀⠐⠀⠀⠀
// ⢀⠃⢿⣷⠈⡄⠓⡀⠆⠱⣈⠒⢠⠑⡈⣾⣿⣞⣷⣻⢾⣽⣳⢯⣿⣿⡟⡘⠤⢁⠒⠤⢁⢃⣼⣿⣟⣷⣿⡿⠿⠛⢋⠍⡩⢉⠍⡩⢙⢻⣿⣷⡷⡄⠀⠀⠐⠀⢀⠈⠀⠀⡀⠈⠀
// ⠠⡉⢄⠻⣷⡌⢂⠥⢉⠒⠤⡉⢄⠊⠔⢻⣿⣞⡷⣯⣟⡾⣽⣯⣿⠏⠰⡐⠌⢢⠁⠎⡠⢿⣿⡿⣽⣿⡿⠁⢆⠩⡐⢌⠰⣈⠰⢀⠃⡜⠻⣿⣷⠃⠀⠀⠠⠀⠀⢀⠈⠀⠀⠀⠀
// ⠠⠑⡂⢌⢹⣿⣖⠰⠈⡌⢂⠅⢢⢉⠰⢉⣿⣯⣟⡷⣯⣟⣷⡟⠡⠌⡁⢆⠩⡄⢃⠜⠠⡙⢿⣿⡿⠋⠤⢉⠄⢢⠁⢎⠐⡄⢢⠁⠎⢠⣽⣿⡇⠀⠀⠀⠄⠀⠂⠀⠠⠀⠀⠀⠀
// ⠐⡡⢘⠠⢂⠌⡙⢠⠃⡰⢁⡘⠄⢢⠁⢆⠘⢿⣯⣿⣷⠟⡉⢄⠣⢘⠰⠈⢆⠘⡠⢊⣥⣶⠿⠋⠤⢉⠔⡨⢘⠠⡉⢄⠊⡄⠃⡌⣸⣼⠿⠟⠋⠀⠀⠀⠄⠂⠀⠂⠀⠐⠀⠈⠀
// ⠠⢃⠜⡠⢃⠄⡃⢄⠸⢀⢻⣄⡸⢀⠃⠜⡘⣀⠛⡘⠠⡘⠠⢄⠸⢀⠜⢃⠄⣣⣤⡿⠟⡀⢄⠛⡠⢘⠠⡀⠇⢠⠃⡜⠠⠘⣃⣤⣿⠇⠀⠀⠀⠀⠠⠀⠀⠀⠀⠄⠃⠀⠀⠀⠀
// ⠦⠡⢎⠰⢁⠎⡰⠈⡔⠨⣀⠛⣿⣿⢾⣶⣴⣤⣮⣴⣥⣢⣑⣢⣌⠢⡘⣼⠟⡋⠍⡐⢂⠅⡊⠔⡁⠆⡑⢠⠉⡔⠂⡔⢡⣳⡾⠋⠀⠀⡀⠠⠀⠀⠐⠀⠈⠀⠀⠂⠀⠀⠁⠀⠀
// ⠒⢡⠂⢎⠐⡊⠔⣁⠢⡑⠄⡊⢌⠻⣿⣼⣭⣛⣼⣭⣟⠿⢛⠋⡩⠄⢡⠂⠜⡠⠑⡌⢨⠐⡡⢘⠠⡑⠨⠄⢃⡰⣡⣾⠟⠋⠀⠀⠠⠀⠀⡀⠀⠁⡀⠠⠀⠀⠄⠠⠀⠠⠁⠀⠀
// ⣙⡄⢋⡄⢣⢉⠒⡄⠢⢑⠨⡐⢢⢁⢂⡉⠍⢋⠍⡡⠂⡜⢀⠣⡐⡘⢄⠊⡔⠡⣁⠢⡁⢆⣡⢢⡱⣴⣷⣿⡿⠟⠋⠀⠀⠀⠀⠀⠄⠀⠀⠀⠠⠀⠀⠀⠀⠄⠀⠀⠠⠀⠀⠀⠀
// ⢥⠊⠥⡈⢆⠡⡃⣌⠱⣈⢂⡑⢢⢈⠄⢢⠉⡄⢊⠤⠑⣈⠢⢡⠐⡡⠌⢒⡈⢒⡀⣾⣿⠻⣜⣧⣿⠿⠛⠉⠀⠀⠀⠀⠐⠀⠈⠀⠀⢀⠀⠁⢀⠀⠂⠈⠀⠀⠐⠈⠀⢀⠈⠀⠀
// ⠦⡙⢢⠑⡌⢢⠑⠤⠒⡄⢢⠐⠢⢌⡘⠤⠡⡘⢄⠢⡑⠄⢆⠡⢊⠔⡈⢆⠘⠤⣰⣿⠿⠛⠛⠁⠀⠀⠀⠀⢀⠀⠂⠈⠀⠀⠠⠈⠀⢀⠀⡀⠀⠀⠀⡀⠠⠀⠄⠀⡈⠀⠀⠀⠀
// ⢣⡑⢢⠑⡘⠤⣉⠒⡡⢘⡀⠎⠱⣀⠒⡄⢣⠐⡌⠒⢌⡘⠠⢃⠌⣂⠱⢈⠆⢲⣿⠃⠀⠀⠀⠀⠀⠠⠀⠀⠀⠀⡀⠀⠂⠀⠄⠀⠄⠀⠀⠀⠀⠐⠀⠀⠄⠀⠠⠀⠀⠐⠀⠀⠀
// ⡥⢊⠤⡉⢆⠱⣀⢣⠐⡡⢄⡉⢒⠠⢡⠘⡠⠡⢌⡑⢂⠌⡑⣈⠒⡠⢃⠢⠌⣻⡿⠀⠦⠁⠀⠐⠀⠀⠠⠀⠁⠀⠀⠄⠐⠀⠀⠀⡀⠠⠀⠂⠁⠀⠂⠀⠀⠂⠀⠀⠁⠀⠂⠈⠀
// ⠲⡡⢢⠑⡌⠒⠤⢢⠑⡐⢂⠌⢢⠑⠢⡁⢆⡑⠢⢌⠢⢘⠰⣀⠣⡐⠡⠌⢂⣿⣷⠀⠀⠀⠀⠀⠂⠁⠀⠐⠀⠁⠀⠀⠀⠀⠠⠀⠀⢀⠀⡀⠈⠀⠐⠈⠀⠐⠈⠀⠁⢀⠂⠀⠀
// ⠛⡱⢃⠫⠜⠫⡜⢣⠚⡘⠄⡊⠔⡨⠑⡐⠢⡐⢡⠂⡜⠠⢡⠐⣂⠡⢃⡘⠤⠘⣟⣷⣎⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//_______________________________________________________________________________________
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
struct DSU{
vector<int>fa;
DSU(int n)
{
for(int i = 0; i <= n; i++)
fa.push_back(i);
}
int found(int x)
{
return fa[x] == x ? x : (fa[x] = found(fa[x]));
}
void merge(int x, int y)
{
x = found(x), y = found(y);
if(x < y){swap(x, y);};
if(x != y)
{
fa[x] = y;
}
}
};
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<int> >g1(n+10);
vector<vector<int> >g2(n+10);
DSU dsu1(n+1);
DSU dsu2(n+1);
for(int i = 0; i < m; i++)
{
int a, b, col;
cin >> a >> b >> col;
if(col == 0)
{
g1[a].push_back(b);
g1[b].push_back(a);
dsu1.merge(a,b);
}
else
{
g2[a].push_back(b);
g2[b].push_back(a);
dsu2.merge(a,b);
}
}
vector<int>vis(n+10);
vector<int>pend;
int ans = 0;
auto dfs = [&](auto &&dfs, int now, int cnt)
{
if(cnt > 4)
return;
pend.push_back(now);
int num = 0;
for(int i = 0; i < cnt; i ++)
{
for(int k = i+1; k < cnt; k++)
{
for(auto j : g2[pend[i]])
{
if(j == pend[k])
{
num++;
break;
}
}
}
}
if(num == cnt-1)
{
// for(int i = 0; i < cnt; i++)
// {
// cout << pend[i] << ' ';
// }
// cout << '\n';
ans++;
}
for(auto i : g1[now])
{
if(!vis[i])
{
vis[i] = 1;
dfs(dfs, i, cnt+1);
vis[i] = 0;
}
}
pend.pop_back();
};
for(int i = 1; i <= n; i++)
{
vis[i] = 1;
dfs(dfs, i, 1);
}
cout << ans << '\n';
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
// int _;
// cin >> _;
// while(_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
3 4 1 2 0 1 3 1 2 3 0 2 3 1
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 6 1 2 0 2 3 0 3 4 0 1 4 1 2 4 1 1 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3580kb
input:
20 28 9 6 1 9 6 0 3 8 0 8 4 0 3 8 1 3 4 1 2 13 0 13 1 0 19 1 0 2 1 1 2 19 1 13 19 1 14 15 1 14 15 0 7 12 0 12 17 0 20 17 0 7 17 1 7 20 1 12 20 1 16 18 0 18 10 0 5 10 0 16 10 1 16 5 1 18 5 1 4 6 0 9 11 0
output:
26
result:
wrong answer 1st numbers differ - expected: '27', found: '26'