Asia Pacific Informatics Olympiad - Time Complexity

[vaibhav Aggarwal]

Hey!

I'm posting my solution to the first problem in the APIO - 2012 (http://d1yjytat4ps3ku.cloudfront.net/final-AeF9DxEp/apio2012-official.pdf)

Please tell me about its time complexity.

Thanks!


#include <iostream>
#include <vector>

#include <queue>
using namespace std;

int main()
{
int n,m;
cin>>n>>m;
vector<int> adls[n+1];
int a,b,c;
int *l=new int[n+1];
int *s=new int[n+1];
for(int i=1;i<=n;i++)
{

cin>>a>>b>>c;
s[i]=b;
l[i]=c;
adls[a].push_back(i);
}

/*for(int i=1;i<=n;i++)
{cout<<"For"<< i<<"th ninja sub ordinate ninjas : ";
for(int j=0;j<adls[i].size();j++)
{
cout<<adls[i][j];
}
cout<<endl;
}*/

int satis=1;
int mm=0;
queue<int> q;
for(int i=1;i<=n;i++)
{satis=1;
priority_queue<int, vector<int>, greater<int> > pq;
q.push(i);
satis=satis*(l[i]);
while(!q.empty()) //for pq filling
{
int top=q.front();

q.pop();
for(int j=0;j<adls[top].size();j++)
{
pq.push(s[adls[top][j]]);
q.push(adls[top][j]);
}
}
int sal=0;
int n=0;
while(!pq.empty())
{
int top=pq.top();
pq.pop();
sal=sal+top;
n++;
if(sal==m)
break;
if(sal>m)
{n--; break;}
}
satis=satis*n;
//cout<<"SATIS : "<<satis<<endl;
mm=max(mm,satis);
}



cout<<mm;






int g;
cin>>g;
}

[blueberry]

please indent, use code tags, and can you tell us what it does? your link doesn’t work.