i just found no of storngly connected components and got ac in 0.562 sec after eliminating stack overflow with pragma.

how to make it so fast as 0.031 sec and so little memory?

Try this test:

Input:
5 1
100 0
100 0
100 0
100 0
100 0
2 50

Output:
250

Hello! I have strange WA 22 and really don't understand why. Can anyone help to find the bug in my code. (corrected)

Edited by author 04.12.2016 20:25

import java.util.*;
import java.io.*;

public class MEGA
{
    public static void main(String arg[])
    {
        int k,n,i,sum=0;
        Scanner scan=new Scanner(System.in);
        k=scan.nextInt();
        n=scan.nextInt();
        int[] a=new int[n];
        for(i=0;i<n;)
        {
            if(scan.hasNextInt())
            {
                a[i]=scan.nextInt();
                i++;
            }
        }
        for(i=0;i<n;i++)
        {
            sum+=a[i]-k;
        }
        if(sum<0)
        {
            System.out.println("1");
        }
        else
        {
            System.out.println(""+sum);
        }
    }
}

This very simple program is turning out to be a headache. What is Test #3?

ll n;
ll ar[300][300];
int main(){
    cin >> n;
    for(ll i = 1; i <= n; i ++) for(ll j = 1; j <= n; j ++) ar[i][j] = 0;
    for(ll i = 1; i <= n; i ++){
        while(1){
            ll x; cin >> x;
            if(x == -1) break;
            ar[x][i] = 1;
        }
    }
    for(ll i = 1; i <= n; i ++) ar[i][n+1] = 1;
    ll col = 1;
    while(col <= n){
        if(ar[col][col] == 1){
            for(ll i = 1; i <= n; i ++){
                if(i == col) continue;
                if(ar[i][col] == 1){
                    //choose ith row
                    for(ll j = 1; j <= n+1; j ++) ar[i][j] = ar[i][j]^ar[col][j];
                }
            }
        }
        else{
            break;
        }
        col ++;
    }
    bool f = 1;
    ll br[300][300];
    for(ll i = 1; i <= n; i ++) for(ll j = 1; j <= n; j ++) if(i==j) br[i][j] = 1;
    for(ll i = 1; i <= n; i ++){
        for(ll j = 1; j <= n; j ++) if(ar[i][j]!=br[i][j]) f = 0;
    }
    if(!f) cout << "No solution" << endl;
    else{
        for(ll i = 1; i <= n; i ++){
            if(ar[i][n+1]==1) cout << i << " ";
        }
    }
    return 0;
}

I have used basic Gauss algorithm making the augmented matrix equal to an identity matrix. Still getting WA. Please help
Thank you :)

Edited by author 04.12.2016 10:11

"If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will LOOSE his head."
http://grammarist.com/usage/loose-lose/

I got AC with a wrong solution during the contest, so I think the test cases might be a bit weak. One example my wrong solution didn't pass is:
7 63713822
It printed 3, while the best answer is 2: 7 -> 8 -> 31856912 -> 31856911 -> 63713822.

Can you please add it to the test-set?

(Edit: I've fixed my solution now, but others may fail.)

Edited by author 03.12.2016 18:42

my code
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, c = 0, s = 0, v = 0, maxn = 0;
    cin >> n;
    string a, b;
    for(int i = 1; i <= n; i++){
        cin >> a ;
        for(int i = 0; i <= a.size(); i++){
        if(a[0] == 'E' && a[1] == 'm' && a[2] == 'p' && a[3] == 'e' ){
            c++;
            break;
        }
        else if( a[0] == 'M' && a[1] == 'a' && a[2] == 'c' && a[3] == 'a'){
            s++;
            break;
        }
        else if(a[0] == 'L' && a[1] == 'i ' && a[2] == 't' && a[3] == 't' ){
            v++;
            break;
        }
        }
        cin >> b;
    }
    if(c > s && c > v){
        cout << "Emperor Penguin";
    }
    else if(s > c && s > v){
        cout << "Macaroni Penguin";
    }
    else if(v > c && v > s){
        cout << "Little Penguin";
    }
    return 0;
}
why incorrect

WA7
3
000
->
000000000002

WA10
0
->
000000000002

Program zadacha;
Var a,b,c,n:integer;
Begin
Readln(n,a,b);
c:=a*b*2*n;
Write(c);
End.

#include<stdio.h>
#include<math.h>
main()
{
    float a,b,c,d;
    scanf("%f%f%f%f", &a,&b,&c,&d);
    printf("%6.4f\n%6.4f\n%6.4f\n%6.4f",sqrt(d), sqrt(c), sqrt(b), sqrt(a));
}
Whats wrong?

Edited by author 27.06.2016 15:47

Edited by author 27.06.2016 15:47

If you are using recursion function to calc the answer, then I suggest you to do it in one of some ways:

1) To write DP without using recursion.
2) To use array of memory and put there -1 if we calced the function of this parametres and 0 if not.
3) if you write in C++, inline may be will help you.

If you have any questions, write.

Edited by author 19.11.2010 01:08

I'm searching the farest node for each node via one dfs and then try to answer the query using this information:

1) if(query_dist > distance_to_farest_node_from_query_vertex)
output 0
2) if query_vertex is ancestor of it's farest node then i return go_up_from(farest_node_from_query_vertex,
dist_to_far_node  -  query_dist)
3) if dist to lca(query_vertex,farest_node_from_query_vertex) enough (d(lca)>=query_dist) just go up from query_vertex in query_dist steps.
4) if(dist to lca is not enough) then go_up_from(
farest_node, farest_node_dist  -  query_dist)
my programm passes my tricky tests,sample test and test from thread. Pls, somebody, give me more tricky tests!

Edited by author 10.10.2010 22:43

123

Now, if you have time limit, use Buffered Reader + Hashset. It is really works.
Если вы столкнулись с Ограничением по времени, попробуйте использовать связку из Buffered Reader + Hashset. Оно реально работает!!!!
Java 1.8.0

I have AC at 0.14 sec, but I can see there are lot of faster solutions.
So how did you optimize your solution so hard ??

I don't know why I got TLE on test 3. I use bruteforce with Python. But in my PC, it runs so fast with n = 20

On test #22,we can extend two segments and get two valid circles,which circle do we choose
??

Hi,

My program pass all local tests but crashes after submit on test #3. Most probably I miss some boundary or weird pattern case. I use C++ and I took into account the fact that char's over 127 are converted to negative integers.

Do you have any hint?

0.499 too close to comfort, i subitted first with GCC compiler got TLE than i submited with VC 2013 and got Accepted

Edited by author 29.11.2016 18:01