GET SET CODE contest : Get Set Code 2021 Coding Competition | CodeChef
Author: TOSHIT KALE
Tester: vallabh43
Editorialist: TOSHIT KALE
DIFFICULTY:
MEDIUM .
PREREQUISITES:
Adjacency list, priority queue.
PROBLEM:
We have a list of levels and also the list which tells what levels need to be completed before completing that level. we have to print the lexicographically smallest order in which we can finish every level otherwise print -1.
QUICK EXPLANATION:
We will construct an adjacency list in which we will tell what levels are required to complete a particular level and the levels whose required criteria are fulfilled, we will add them in the priority queue so that we get lexicographically smallest order.
EXPLANATION:
As we make an adjacency list we make the connection between a level and its required level, we also create a priority queue which will include the levels which require 0 levels in the beginning then as we complete the criteria for any other level we will add it in the priority queue and decrease the count of level.
So here is the time complexity for creating adjacency list O(n) and for iterating through priority queue O(n)*O(logn).so time complexity is O(nlogn).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fio ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define MP make_pair
const int maxn = 1e5 + 10;
int main(){
fio
int t=1 ;
cin >> t;
while(t --){
int n;
cin >> n;
vector<int> g[n + 10],output;
int a[n + 10];
priority_queue<int> q;
for(int i = 1 ; i <= n ; i ++){
int k;
cin >> k;
a[i] = k;
if(!k){
q.push(-i);
}
for(int j = 0 ; j < k ; j ++){
int x;
cin >> x;
g[x].push_back(i);
}
}
while(!q.empty()){
int v = q.top();
output.push_back(-v);
q.pop();
for(int i : g[-v]){
a[i] = a[i] - 1;
if(!(a[i]))
q.push(-i);
}
}
int ans = 0;
for(int i = 1 ; i <= n ; i ++){
if(a[i]){
ans = -1;
break;
}
}
if(ans==-1)cout<<-1<<endl;
else {
for(int i=0;i<n;i++)cout<<output[i]<<" ";
cout<<endl;
}
continue;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fst first
#define snd second
#define mp make_pair
#define MOD 1000000007
#define all(v) (v).begin(),(v).end()
#define frl(i,n) for(long long i=0;i<n;i++)
#define ms(x,i) memset(x,i,sizeof(x))
#define dbg(x) cerr << #x << " = " << x << "\n"
#define displayvec(vec) cerr<<#vec<<": "; for(auto vd : vec) cerr<<vd<<" "; cerr<<"\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
void oJudge() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
}
void solve(){
int n;
cin>>n;
vector< vector< int > > adj(n+1);
vector< int > pre(n+1), done(n+1), sol;
for(int i = 1; i <= n; ++i){
int x;
cin>>x;
while(x--){
int k;
cin>>k;
adj[k].push_back(i);
++pre[i];
}
}
priority_queue< int, vector< int >, greater< int > > q;
for(int i = 1; i <= n; ++i){
if(!pre[i]){
q.push(i);
}
}
while(!q.empty()){
int x = q.top();
q.pop();
sol.push_back(x);
vector< int > v;
for(auto i : adj[x]){
if(--pre[i] == 0 && done[i] == 0){
v.push_back(i);
done[i] = 1;
}
}
sort(all(v));
for(auto i : v){
q.push(i);
}
}
if(sol.size() < n){
cout<<"-1\n";
}
else{
for(auto i : sol){
cout<<i<<" ";
}
cout<<"\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//oJudge();
int t = 1;
cin>>t;
while(t--){
solve();
}
return 0;
}