# Q1 DAA Mock Contest 3

unknown
c_cpp
2 months ago
2.4 kB
5
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define int long long
int N, E, Q;
vector<int> indegree;
stack<int> ans;
vector<int> vis;

vector<int> toposort(bool ascending) {
vector<int> ans;
if(ascending) {
priority_queue<int, vector<int>, greater<int>> pq;
for(int i = 0; i < N; i++) {
if(indegree[i] == 0) {
pq.push(i);
}
}

while(!pq.empty()) {
int curr = pq.top(); pq.pop();
ans.push_back(curr);
indegree[v]--;
if(indegree[v] == 0) pq.push(v);
}
}
}
else {
priority_queue<int> pq;
for(int i = 0; i < N; i++) {
if(indegree[i] == 0) {
pq.push(i);
}
}

while(!pq.empty()) {
int curr = pq.top(); pq.pop();
ans.push_back(curr);
indegree[v]--;
if(indegree[v] == 0) pq.push(v);
}
}
}
return ans;
}

void solve_q1() {
vector<int> r = toposort(true);

if((int)r.size() != N) {
cout << -1 << '\n';
return;
}

int n = r.size();
vector<int> a(n, 1), b(n, 1);
for(int i = 1; i < n; i++) {
if(r[i] > r[i - 1]) a[i] = a[i - 1] + 1;
}
for(int i = n - 2; i >= 0; i--) {
if(r[i] > r[i + 1]) b[i] = b[i + 1] + 1;
}

int ans = 0;
for(int i = 0; i < n; i++) {
ans += max(a[i], b[i]);
}

cout << ans << '\n';
}

void solve_q2() {
vector<int> nums = toposort(false);
int end = 0, far = 0, ans = 0;
for(int i = 0; i < (int)nums.size() - 1; i++) {
far = max(far, i + nums[i]);
if(i == end) {
ans++;
end = far;
}
}
cout << ans << '\n';
}

signed main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
cin >> N >> E >> Q;