I am doing standard BFS, and then finding the max of all min over all shortest paths

#include <bits/stdc++.h>(ignore this)
using namespace std;

void solve() {
    int n;
    int m;
    cin >> n >> m;
    vector<vector<int>> adj(n+1);
    for(int i=0;i<m;i++){
        int a;
        int b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<bool> vis(n+1,false);
    int s;
    int f;
    int r;
    cin >> s >> f >> r;
    vector<int> ds(n+1,0);
    vector<int> dr(n+1,0);
    //BFS from s
    queue<pair<int,int>> q;
    q.push({0,s});
    ds[s] = 0;
    while(!q.empty()){
        pair<int,int> v = q.front();
        q.pop();
        for(int j : adj[v.second]){
            if(vis[j] == false){
                ds[j] = v.first+1;
                vis[j] = true;
                q.push({ds[j],j});
            }
        }
    }
    for(int i=1;i<=n;i++){
        vis[i] = false;
    }
    // BFS from r
    q.push({0,r});
    dr[r] = 0;
    while(!q.empty()){
        pair<int,int> v = q.front();
        q.pop();
        for(int j : adj[v.second]){
            if(vis[j] == false){
                dr[j] = v.first+1;
                vis[j] = true;
                q.push({dr[j],j});
            }
        }
    }
    for(int i=1;i<=n;i++){
        vis[i] = false;
    }
    if(s == f){
        cout << dr[s] << endl;
        return;
    }
    int ans = -1;
    // Final BFS
    q.push({dr[s],s});
    bool found_f = false;
    while(!found_f){
        int k = q.size();
        while(k--){
            pair<int,int> v = q.front();
            q.pop();
            for(int j : adj[v.second]){
                q.push({min(dr[j],v.first),j});
                if(j == f){
                    found_f = true;
                }
            }
        }
    }
    int k = q.size();
    while(k--){
        pair<int,int> v = q.front();
        q.pop();
        if(v.second == f) ans = max(ans,v.first);
    }
    cout << ans << endl;
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Edited by author 09.07.2025 00:48

input:
1000000000000000000

output:
524638269999999991

optimized search + cross product)

To read the input in C++, the following helped me: unsigned char x = cin.get().

Then I used some ifs in the form of if (x == 218) { ... }

Also, the first test case seems to be different from the one suggested in the statement.

i use DP.

b = input()
s = ''
d = []
for i in b:
    s += i
    if s == s[::-1]:
        d.append(s)
    if s != s[::-1] and len(s) % 2 != 0:
        s = s[1:]
    if s == s[::-1]:
        d.append(s)
    if s != s[::-1] and len(s) % 2 != 0:
        s = s[1:]
m = max(d, key=len)
if len(m) <= 1000:
    print(m)

see what your program outputs for an integer answer
ps it should output .00

посмотрите, что выводит ваша программа при целом ответе
ps она должна выводить .00

1)
4 4
1 2 9 15
1 4 0 8
2 3 20 30
3 1 31 0
1 4 9 30

->
4
1 3 4 2

2)
2 3
1 2 0 5
1 1 110 80
1 1 90 0
1 2 100 6

->
3
2 3 1

3)
3 6
1 2 50 55
2 1 55 40
1 2 0 1
1 3 41 80
3 2 80 12
2 1 15 0
1 2 49 7

->
6
1 2 4 5 6 3

Finally I've solved this problem using very hard optimised Main & Lorentz's algo, and 0.405s only.

But I noticed many people solved this problem very fast and using much less memory.
What algo do you use? I doubt it's possible to speed-up Main & Lorentz or Crochemore algos so much.

Is it some alternative (like suffix tree) solution, or just some strong idea can be applied to this particular problem? Is it possible to solve it in O(n)?

1 5
/\/\X
.\X\\
ans: 4

#include <bits/stdc++.h>
using namespace std;

int cal(int x){
    int ret = 0;
    while (x > 0){
        ret += x % 10;
        x /= 10;
    }
    return ret;
}

bool lucky(int x, int mm){
    int a = x / mm;
    int b = x % mm;
    if (cal(a) == cal(b)) return true;
    return false;
}

int main(){
    int n;
    cin >> n;
    int nn = round(pow(10, n)) - 1;
    int mm = round(pow(10, n / 2));
    int tot = 0;
    for (int i = 0; i <= nn; i++){
        if (lucky(i, mm)) tot++;
    }
    cout << tot << endl;
}

if your code is simple and fast enough, brute force can work.

what is wrong with my code:

#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <unordered_map>
#define ll long long
#define fri(a, b) for (ll i = a; i < b; i++)
#define frj(a, b) for (ll j = a; j < b; j++)
#define frk(a, b) for (int k = a; k < b; k++)
#define frh(a, b) for (int h = a; h < b; h++)
#define frz(a, b) for (int z = a; z < b; z++)
#define rfri(a, b) for (int i = a; i >= b; i--)
#define rfrj(a, b) for (int j = a; j >= b; j--)
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
const int mod=100000007;
using namespace std;
ll dp[50][1005];

ll func(ll n,ll s){
  if(dp[n][s] != -1) return dp[n][s];
  if(s == 0) return 1;
  if(n == 0){
    if(s == 0) return 1;
    else return 0;
  }
  ll ans = 0;
  fri(0,10){
    if((s - i) >= 0) ans = (ans + func(n-1,s-i)) ;
  }
  return dp[n][s] = ans;
}

int main() {
    fast
    ll T = 1;
    // cin >> T;

    frz(0,T){
      ll n,s;
      cin >> n >> s;
      memset(dp,-1,sizeof(dp));
      if(s%2) cout << 0 << "\n";
      else {
        ll ans = func(n,s/2);
        cout << (ans*ans) << "\n";
      }
    }
}

For example:
16
9001 9001
8999 8999
9001 8999
8999 9001
-9001 -9001
-9001 -8999
-8999 -9001
-8999 -8999
9001 -9001
8999 -8999
9001 -8999
8999 -9001
-9001 9001
-8999 8999
-9001 8999
-8999 9001
5
9000 9000
9000 -9000
-9000 -9000
-9000 9000
0 0

My AC program gives answer:
1 2 3 4
9 10 11 12
5 6 7 8
13 14 15 16
2

But right answer:
1 2 3 4
9 10 11 12
5 6 7 8
13 14 15 16
2 8 10 14

 First I wrote the program in Java, but I got TLE on test #9, below is my program that gets TLE:

import java.util.Scanner;

public class Main {

    public static int read(int idx, int[] tree){
        int sum = 0;
        while(idx > 0){
            sum += tree[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }

    public static void update(int idx, int maxIndex, int[] tree){
        while(idx <= maxIndex){
            tree[idx]++;
            idx += idx & (-idx);
        }
    }

    public static void main(String[] args) {
        int N;
        int maxIndex = 32005;

        int[] level;
        int[] binaryIndexTree;

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        level = new int[N+1];
        binaryIndexTree = new int[maxIndex];

        for(int i=0; i<N; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            x++;
            level[ read(x, binaryIndexTree) ]++;
            update(x, maxIndex, binaryIndexTree);
        }
        for(int i=0; i<N; i++){
            System.out.println(level[i]);
        }

    }
}

Then I write in C++ and get AC?
@admins: Please extend time limit for Java.

I tried with precalculating with map for setting up the index with 1 only rest will be auto 0 but miraculously WA at 4. so i figured out that the author only wants you to solve with his idea only. So good luck.

Hi, Admins.
Please, add these case:
N > 5*10^4
a[i] = 1, for i = 1.. N-1, and
a[N] = 10^9

Q = N
p[i] = i,  x[i] = i

For example:
77888
1 1 1 1 1 1 .... 1 1 77888
77888
1 1
2 2
3 3
4 4
5 5
...
77888 77888

my solution takes 0.031 seconds.

Can Anyone be kind enough to explain this ques to me? I'll be grateful to you..

DO your own solve then check this do not cheat yourself
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define FastAF ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

template <typename T> // cin >> vector<T>
istream &operator>>(istream &istream, vector<T> &v){for (auto &it : v) cin >> it;return istream;}
template <typename T> // cout << vector<T>
ostream &operator<<(ostream &ostream, const vector<T> &c){for (auto &it : c) cout << it << " ";return ostream;}

const int mx=2e5;

int ar[mx];
void d(){
    ar[0]=2;
    int k=1;
    for(int i=3;i<mx;i++){
        bool f=true;
        for(int j=2;j*j<=i;j++){
            if(i%j==0){
                f=false;
                break;
            }
        }
        if(f){
            ar[k++]=i;
        }
    }
}

int main(){
    FastAF
    d();
    int n;
    cin>>n;
    while(n--){
        int a;cin>>a;
        cout<<ar[--a]<<endl;
    }
return 0;
}

Algo: sqrt with precomputation

Edited by author 11.05.2025 11:58

Edited by author 11.05.2025 12:02