Page 3 of 3

Re: 10973 - Triangle Counting

Posted: Sat Jun 15, 2013 12:10 pm
by Hikari9
Just a tip, especially for those who get TLE and RTE

1. A brute force O(n^3) approach can get Accepted (with use of scanf and good memory allocation)
2. Vertices in the input CAN be greater than n (check problem description)
3. You only need to count triangles up to vertex n

Re: 10973 - Triangle Counting

Posted: Sat Jan 17, 2015 11:00 am
by matheusdallrosa
Hikari9 wrote:Just a tip, especially for those who get TLE and RTE

1. A brute force O(n^3) approach can get Accepted (with use of scanf and good memory allocation)
2. Vertices in the input CAN be greater than n (check problem description)
3. You only need to count triangles up to vertex n
About the first item: make a linked list using new for node allocation you'll get a better time.