Task: | Peli |
Sender: | adex720 |
Submission time: | 2024-01-20 15:03:47 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | ACCEPTED | 0.01 s | 1, 2 | details |
#3 | TIME LIMIT EXCEEDED | -- | 2 | details |
#4 | ACCEPTED | 0.00 s | 1, 2 | details |
#5 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#6 | TIME LIMIT EXCEEDED | -- | 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | ACCEPTED | 0.01 s | 1, 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | TIME LIMIT EXCEEDED | -- | 2 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:85:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare] 85 | if (reitit[i2].size() > i) | ~~~~~~~~~~~~~~~~~~^~~
Code
#include <bits/stdc++.h> #include <iostream> #include <vector> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, kyselyja, x, a, b; cin >> n >> m >> kyselyja; vector<int> v[n]; for (int i = 0; i < m; i++) { cin >> a >> b; a--; b--; v[a].push_back(b); v[b].push_back(a); } // käydään jokainen kysely läpi for (int i = 0; i < kyselyja; i++) { cin >> a >> b >> x; a--; b--; if (x == 0) { if (a == b) { cout << "YES\n"; } else { cout << "NO\n"; } continue; } // etsitään lyhyimmän reitin pituus priority_queue<pair<int, int>> q; int kayty[n]; int arvot[n]; fill(kayty, kayty + n, 0); kayty[a] = 1; arvot[a] = 0; vector<int> reitit[n]; int tulo[n]; fill(tulo, tulo + n, -1); for (int vierus : v[a]) { q.push(make_pair(-1, vierus)); tulo[vierus] = a; } int lyhyin = a == b ? 0 : -1; int pienin_lisays = INT_MAX; while (!q.empty()) { auto t = q.top(); q.pop(); if (-t.first > x) { break; } if (kayty[t.second]) { int d = -t.first + arvot[t.second]; int raja = min(-t.first - 1, arvot[t.second]); for (int i = 0; i < raja; i++) { int i2 = tulo[t.second]; if (reitit[i2].size() > i) { i2 = reitit[i2].at(i); } if (reitit[t.second].at(i) == i2) { d -= 2; } } if ((d & 1) && d < pienin_lisays) { pienin_lisays = d; } continue; } else { for (int val : reitit[tulo[t.second]]) { reitit[t.second].push_back(val); } reitit[t.second].push_back(tulo[t.second]); } if (t.second == b && lyhyin == -1) { lyhyin = -t.first; } kayty[t.second] = 1; arvot[t.second] = -t.first; for (int vierus : v[t.second]) { q.push(make_pair(t.first - 1, vierus)); if (tulo[vierus] == -1) { tulo[vierus] = t.second; } } } if (lyhyin == -1) { cout << "NO\n"; continue; } if (lyhyin > x) { cout << "NO\n"; continue; } if (((x - lyhyin) & 1) == 0) { cout << "YES\n"; continue; } if ((x - lyhyin) >= pienin_lisays) { cout << "YES\n"; continue; } cout << "NO\n"; } } /* 5 5 2 1 2 2 3 3 5 1 4 4 5 */
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
2 1 100 1 2 1 1 0 1 2 0 2 1 0 ... |
correct output |
---|
YES NO NO YES NO ... |
user output |
---|
YES NO NO YES NO ... Truncated |
Test 2
Group: 1, 2
Verdict: ACCEPTED
input |
---|
50 49 100 33 34 7 8 49 50 47 48 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... Truncated |
Test 3
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2500 2499 100000 821 822 2351 2352 752 753 832 833 ... |
correct output |
---|
NO YES YES NO NO ... |
user output |
---|
(empty) |
Test 4
Group: 1, 2
Verdict: ACCEPTED
input |
---|
12 12 100 9 10 2 3 1 12 1 2 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... Truncated |
Test 5
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
11 11 100 10 11 7 8 1 2 5 6 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... Truncated |
Test 6
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2500 2500 100000 1936 1937 1884 1885 751 752 831 832 ... |
correct output |
---|
NO YES YES NO NO ... |
user output |
---|
(empty) |
Test 7
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2499 2499 100000 821 822 2351 2352 752 753 832 833 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
(empty) |
Test 8
Group: 1, 2
Verdict: ACCEPTED
input |
---|
50 99 100 40 47 34 50 44 47 15 16 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... Truncated |
Test 9
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2500 4999 100000 1191 2361 251 399 1026 2300 82 1655 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
(empty) |
Test 10
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
2500 4999 100000 2023 2218 23 51 1020 1272 11 114 ... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
(empty) |