Submission #995650
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; #define mp make_pair #define pb push_back #define N 100010 int n; int a[N], b[N]; map<PII, set<int> > A; void end() { puts ("-1"); exit(0); } int path[N], L; bool v[N]; vector<int> c[N]; // c[i] = connect with path[i] and path[i+1] int sc[N]; int main() { cin >> n; for (int i = 0; i < n; i ++) { cin >> a[i] >> b[i]; A[mp(a[i], b[i])].insert(i); } if (a[0] != 0 || b[1] != 0 || a[1] != b[0]) end(); L = a[1]; path[0] = 0; path[L] = 1; for (int i = 1; i < L; i++) path[i] = -1; for (int i = 2; i < n; i++) if (a[i] + b[i] == L) { if (path[a[i]] == -1) { path[a[i]] = i; v[i] = true; } } for (int i = 1; i < L; i ++) if (path[i] == -1) end(); for (int i = 2; i < n; i ++) { if (a[i] == 0 || b[i] == 0) end(); if (a[i] + b[i] < L) end(); } int S = 0; S += L; // path for (int i = 2; i < n; i ++) { if (a[i] + b[i] == L) { S += 2; } else if (a[i] + b[i] == L+1) { S += 2; c[a[i]-1].pb(i); } else { if (A.find(mp(a[i]-1, b[i]-1)) != A.end()) { S ++; } else { end(); } } } for (int i = 0; i < L; i ++) { sc[i] = (int) c[i].size(); } for (int i = 0; i < L-1; i ++) { int T = min(sc[i], sc[i+1]); S -= T; } cout << S << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Distance Pairs |
User | tourist |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1465 Byte |
Status | WA |
Exec Time | 156 ms |
Memory | 18304 KB |
Judge Result
Set Name | sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1500 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt |
All | sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 126 ms | 17792 KB |
01-02.txt | AC | 77 ms | 8064 KB |
01-03.txt | AC | 5 ms | 2560 KB |
01-04.txt | AC | 5 ms | 2560 KB |
01-05.txt | WA | 6 ms | 2688 KB |
01-06.txt | WA | 41 ms | 5760 KB |
01-07.txt | WA | 95 ms | 8576 KB |
01-08.txt | WA | 92 ms | 8704 KB |
01-09.txt | WA | 86 ms | 8320 KB |
01-10.txt | WA | 74 ms | 8064 KB |
01-11.txt | WA | 100 ms | 8320 KB |
01-12.txt | WA | 100 ms | 8320 KB |
01-13.txt | WA | 156 ms | 17664 KB |
01-14.txt | WA | 127 ms | 18304 KB |
01-15.txt | AC | 154 ms | 17408 KB |
01-16.txt | WA | 70 ms | 8064 KB |
01-17.txt | WA | 72 ms | 8064 KB |
01-18.txt | AC | 75 ms | 8700 KB |
01-19.txt | WA | 133 ms | 17664 KB |
01-20.txt | WA | 123 ms | 15744 KB |
01-21.txt | WA | 131 ms | 16000 KB |
01-22.txt | WA | 111 ms | 12288 KB |
01-23.txt | AC | 92 ms | 8704 KB |
01-24.txt | AC | 91 ms | 8704 KB |
01-25.txt | AC | 91 ms | 8448 KB |
01-26.txt | AC | 92 ms | 8448 KB |
01-27.txt | AC | 89 ms | 8576 KB |
01-28.txt | AC | 92 ms | 8704 KB |
01-29.txt | WA | 5 ms | 2560 KB |
01-30.txt | AC | 5 ms | 2560 KB |
01-31.txt | AC | 5 ms | 2560 KB |
sample-01.txt | AC | 5 ms | 2560 KB |
sample-02.txt | AC | 5 ms | 2560 KB |