i couldn't understand, why my programm got Runtime error 15. When i increased MAXN from 1e4 + 10 to 1e5 + 10, i got AC. So the vertices number are in the range [1, 1e5], but not in [1, 1e4], as written in the statement

I got stuck with RE#15 (dp+dfs).
Non-recursive algo with same idea got AC.
Hope this information helped.

5
1 2 1 3 2
ans: 1 2

Maybe someone could explain why I'm still getting WA 13? On all of tests in this forum i get right answers. Can anyone give more tests?

For WA3 try this:
3
1 2 1
Ans:
1
For WA12 try this:
5 1 2 3 1 5
Ans:
1 5

17
1 2 3 4 5 6 7 2 8 9 5 10 8 9 11 3 9

1 2 8 9

1 2 3 9

??????????????????????????????????????

HELP

Give me this test

Please help

#include <bits/stdc++.h>
using namespace std;
const int infInt = 1<<30;
vector<int>adj[100010];
pair<int,int> edges[100010];
int parent[100010],dist[100010];
map< pair<int,int> ,int> Map;
bool mark[100010];


void path(int u){
  if(parent[u]==u){
    cout<<edges[u].first<<" "<<edges[u].second;
    return;
  }
  path(parent[u]);
  cout<<" "<<edges[u].second;
}
int main(){
  int ant,curr,root,n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>curr;
    if(i>0){
      edges[i].first=ant;
      edges[i].second=curr;
      adj[ant].push_back(curr);
      Map[make_pair(ant,curr)]=i;
    }

    if(i==0)
      root=curr;
    ant=curr;
  }
  if(root==curr){
    cout<<root<<endl;
    return 0;
  }
  queue<int> q;
  for(int i=1;i<n;i++){
    parent[i]=i;
    dist[i]=infInt;
    if(edges[i].first==root){
      q.push(i);
      dist[i]=0;
    }
    if(edges[i].second==curr)
      mark[i]=true;
  }

  while(!q.empty()){
    int u=q.front();
    q.pop();
    int x=edges[u].first;
    int y=edges[u].second;
    for(auto z: adj[y]){
      int v=Map[make_pair(y,z)];
      if(v>u and dist[v]>dist[u]+1){
        dist[v]=dist[u]+1;
        parent[v]=u;
        q.push(v);
      }
    }
  }
  int best=infInt,bestInd=-1;
  for(int i=1;i<n;i++){
    if(dist[i]<best and mark[i]){
      bestInd=i;
      best=dist[i];
    }
  }
  path(bestInd);
  cout<<endl;
  return 0;
}

Could anyone provide me with an O(n) solution? My works O(n log(n))

My solution is O(n) and I can prove it.
All tests from forum were successfully passed.
Solution's body is 31 strings (without var declaratoins, etc.) and I am looking for mistakes more than an hour. So I suppose, there is no bug..(

But I have WA5.
Mabe some incorrect input ? Or some thing I didn't notice ?
If u have got any idea or maybe test, please, help..

Edited by author 14.08.2009 05:39

what's is the wrong with this solution ?: i find the shortest path from the first vertx in the chain to the last ( with bfs) an print that path.i read my code , and I think it's correct ,say if I misunderstood the problem

please help！I can't find the bug.

Edited by author 10.09.2015 07:36

My code got WA7.
const Nmax=100500;
var
 Dp:array[1..Nmax] of longint;
 A,V:array[1..Nmax] of longint;
 N,i:longint;

BEGIN
 readln(N);
 for i:=1 to N do
 begin
  read(A[i]);
  Dp[a[i]]:=Nmax+5;
 end;

 Dp[a[n]]:=0;
 V[a[n]]:=0;
 for i:=N-1 downto 1 do
 begin
  if(Dp[a[i]]>Dp[a[i+1]]+1) then begin
   Dp[a[i]]:=Dp[a[i+1]]+1;
   V[a[i]]:=a[i+1];
  end;
 end;

 write(a[1],' ');
 i:=V[a[1]];
 while(i<>0) do begin
  write(i,' ');
  i:=V[i];
 end;
END.

Hi I can pass my test case on every test in this forum, but it fails on #16. Can someone give me the testcase?

I use dp code.
///////////////////


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;


public class Timus_1651 {
    static StreamTokenizer st;
    public static void main(String[] args) throws IOException{
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = nextInt();
        int []a = new int [n+1];
        for (int i = 1; i <=n; i++) {
            a[i] = nextInt();
        }
        int []dp = new int [100001];
        int []p = new int [100001];
        int INF  = (int)1e8;
        Arrays.fill(dp, INF);
        dp[a[1]] = 0;
        for (int i = 2; i <=n; i++) {
            if (dp[a[i]] > dp[a[i-1]]+1){
                dp[a[i]] = dp[a[i-1]]+1;
                p[a[i]] = a[i-1];
            }
        }
        int cur = a[n];
        ArrayList<Integer> ans = new ArrayList<Integer>();
        while (true){
            ans.add(cur);
            if (cur == a[1]) break;
            cur = p[cur];
        }
        Collections.reverse(ans);
        for (int i = 0; i < ans.size(); i++) {
            out.write(ans.get(i)+" ");
        }
        out.close();
    }
    private static int nextInt() throws IOException{
        st.nextToken();
        return (int) st.nval;
    }

}

who can help me?
I use bfs.

AC in 0.14... but on my tests my program works > 2 sec.
If I understand statements right, this test is correct:

#include <cstdio>

int main()
{
  int n = 10000, sum = 0;

  printf("%d\n", 99951);
  for (int i = 6; i <= n; i++)
  {
    printf("1 %d 2 %d 3 %d 4 %d 5 %d ", i, i, i, i, i);
    sum += 10;
  }
  puts("1");
  sum++;
  fprintf(stderr, "%d\n", sum);
  return 0;
}