Submission #995664
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; #define mp make_pair #define pb push_back #define fi first #define se second #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]; map<PII, set<int> > B; 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.find(mp(a[i]-1, b[i]-1)) != A.end()) { S ++; } else if (A.find(mp(a[i]-1, b[i])) != A.end() && A.find(mp(a[i], b[i]-1)) != A.end()) { S += 2; B[mp(a[i], b[i])].insert(i); } 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; } */ for (map<PII, set<int> >::iterator i = B.begin(); i != B.end(); i++) { int l = i->fi.fi; int r = i->fi.se; if (B.find(mp(l+1,r-1)) != B.end()) { S -= min( (int) i->se.size(), (int) B[mp(l+1,r-1)].size()); } } 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 | 1861 Byte |
Status | WA |
Exec Time | 167 ms |
Memory | 17152 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 | 129 ms | 15488 KB |
01-02.txt | AC | 75 ms | 5760 KB |
01-03.txt | AC | 3 ms | 256 KB |
01-04.txt | AC | 3 ms | 256 KB |
01-05.txt | WA | 3 ms | 384 KB |
01-06.txt | WA | 39 ms | 3456 KB |
01-07.txt | WA | 93 ms | 6272 KB |
01-08.txt | WA | 90 ms | 6272 KB |
01-09.txt | WA | 85 ms | 5888 KB |
01-10.txt | WA | 73 ms | 5760 KB |
01-11.txt | WA | 99 ms | 6016 KB |
01-12.txt | WA | 97 ms | 6016 KB |
01-13.txt | WA | 153 ms | 15232 KB |
01-14.txt | WA | 128 ms | 15616 KB |
01-15.txt | AC | 157 ms | 15104 KB |
01-16.txt | WA | 69 ms | 5760 KB |
01-17.txt | WA | 69 ms | 5760 KB |
01-18.txt | AC | 99 ms | 10368 KB |
01-19.txt | WA | 127 ms | 15232 KB |
01-20.txt | WA | 165 ms | 16896 KB |
01-21.txt | WA | 167 ms | 17152 KB |
01-22.txt | WA | 156 ms | 13056 KB |
01-23.txt | AC | 91 ms | 6272 KB |
01-24.txt | AC | 88 ms | 6272 KB |
01-25.txt | AC | 88 ms | 6144 KB |
01-26.txt | AC | 89 ms | 6144 KB |
01-27.txt | AC | 88 ms | 6272 KB |
01-28.txt | AC | 89 ms | 6272 KB |
01-29.txt | WA | 3 ms | 256 KB |
01-30.txt | AC | 2 ms | 256 KB |
01-31.txt | AC | 3 ms | 256 KB |
sample-01.txt | AC | 3 ms | 256 KB |
sample-02.txt | AC | 3 ms | 256 KB |