QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#74725 | #5002. Distance and Tree | Smallbasic# | ML | 2ms | 5472kb | C++14 | 1.3kb | 2023-02-03 15:45:37 | 2023-02-03 15:45:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
inline int read() {
register int s = 0, f = 1; register char ch = getchar();
while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
return s * f;
}
int n, d[N], fr[N], to[N], top = 0;
inline void addedge(int from, int t) {
fr[++top] = from; to[top] = t;
}
inline int abs_(int a) {
return a < 0 ? -a : a;
}
inline bool calc(int L, vector<int> p) {
vector<int> q; int t = -1;
bool res = 1;
for (int i : p) {
if (d[i] == d[L] + 1) {
addedge(L, i); t = i;
if (!q.empty()) {
res &= calc(i, q);
if (!res) return 0;
}
q.clear();
} else q.push_back(i);
} if (!q.empty()) {
if (t == -1) return 0;
return calc(t, q);
} return 1;
}
int main() {
n = read();
for (int i = 1; i <= n; ++i) d[i] = read();
int rt = 0;
for (int i = 1; i <= n; ++i) {
if (!d[i]) rt = i;
}
if (!rt) puts("-1");
else {
vector<int> p;
for (int i = rt + 1; i <= n; ++i)
p.push_back(i);
for (int i = 1; i < rt; ++i)
p.push_back(i);
if (!calc(rt, p)) puts("-1");
else {
for (int i = 1; i < n; ++i)
printf("%d %d\n", fr[i], to[i]);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5328kb
input:
5 0 1 2 1 3
output:
-1
result:
ok Accepted
Test #2:
score: 0
Accepted
time: 2ms
memory: 5472kb
input:
5 1 1 0 1 1
output:
3 4 3 5 3 1 3 2
result:
ok Accepted
Test #3:
score: -100
Memory Limit Exceeded
input:
100000 96770 96764 96762 96761 96759 96755 96754 96753 96752 96751 96750 96748 96746 96745 96741 96740 96739 96736 96735 96734 96730 96728 96727 96726 96723 96718 96714 96712 96710 96709 96706 96705 96704 96703 96702 96698 96697 96696 96695 96693 96692 96690 96687 96684 96683 96682 96681 96679 96677...