Submission #995729
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 (!v[i]) { if (a[i] + b[i] == L) { S += 2; B[mp(a[i], b[i])].insert(i); } else { if (A.find(mp(a[i]-1, b[i]-1)) != A.end()) { S ++; B[mp(a[i], b[i])].insert(i); } 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 | 1944 Byte |
Status | WA |
Exec Time | 219 ms |
Memory | 29184 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 | 122 ms | 15488 KB |
01-02.txt | AC | 75 ms | 5760 KB |
01-03.txt | AC | 2 ms | 256 KB |
01-04.txt | AC | 2 ms | 256 KB |
01-05.txt | WA | 3 ms | 384 KB |
01-06.txt | WA | 49 ms | 6144 KB |
01-07.txt | WA | 93 ms | 6272 KB |
01-08.txt | WA | 90 ms | 6400 KB |
01-09.txt | WA | 84 ms | 6016 KB |
01-10.txt | WA | 96 ms | 10496 KB |
01-11.txt | WA | 138 ms | 10752 KB |
01-12.txt | WA | 135 ms | 10880 KB |
01-13.txt | AC | 214 ms | 28032 KB |
01-14.txt | AC | 122 ms | 15616 KB |
01-15.txt | AC | 219 ms | 29184 KB |
01-16.txt | AC | 92 ms | 10368 KB |
01-17.txt | AC | 94 ms | 10368 KB |
01-18.txt | AC | 95 ms | 10368 KB |
01-19.txt | WA | 122 ms | 15232 KB |
01-20.txt | WA | 195 ms | 22144 KB |
01-21.txt | WA | 195 ms | 22528 KB |
01-22.txt | WA | 181 ms | 17024 KB |
01-23.txt | AC | 91 ms | 6528 KB |
01-24.txt | AC | 89 ms | 6400 KB |
01-25.txt | AC | 88 ms | 6144 KB |
01-26.txt | AC | 89 ms | 6144 KB |
01-27.txt | AC | 88 ms | 6144 KB |
01-28.txt | AC | 90 ms | 6272 KB |
01-29.txt | WA | 2 ms | 256 KB |
01-30.txt | AC | 2 ms | 256 KB |
01-31.txt | AC | 2 ms | 256 KB |
sample-01.txt | AC | 2 ms | 256 KB |
sample-02.txt | AC | 2 ms | 256 KB |