Out of all shortest path I am finding min of maximum distance I have to travel for every level.





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

void bfs(int u,vector<int> &d,const vector<vector<int>> adj){
    d[u] = 0;
    queue<int> q;
    q.push(u);

    while(!q.empty()){
        int u = q.front();
        q.pop();

        for(auto v:adj[u]){
            if(d[v]>d[u]+1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n);

    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u-1].push_back(v-1);
        adj[v-1].push_back(u-1);
    }

    vector<int> ds(n,1e9),df(n,1e9),dr(n,1e9);
    int s,f,r;
    cin>>s>>f>>r;
    s--,f--,r--;
    bfs(s,ds,adj);
    bfs(f,df,adj);
    bfs(r,dr,adj);

    vector<vector<int>> l(ds[f]+1);

    for(int i=0;i<n;i++){
        if(ds[i]+df[i]==ds[f]){
            l[ds[i]].push_back(i);
        }
    }
    int ans = INT_MAX;
    for(int i=0;i<=ds[f];i++){
        int a = INT_MIN;
        for(auto x: l[i]){
            a = max(a,dr[x]);
        }
        ans = min(a,ans);
    }

    cout<<ans;

    return 0;
}

when it may be «It is a lie!».

Does anybody have an idea ?

Edited by author 04.04.2010 08:24

Solution is pretty straightforward based on parity and bit position, but to avoid all those position reflections in your head during coding, generate codes for say N=5 and look at value of "k XOR x"

i found mistake :)


Edited by author 07.08.2022 13:48

Are there beautifull solution? The one other from bruteforce

My solution is O(tl^3logn) , but its performance is good.

If you look at the statement, it says "Triviality of a natural number N is the ratio of the sum of all its proper divisors to the number itself. Recall that a proper divisor of a natural number is the divisor that is strictly less than the number.". Therefore, triviality of 1 should be 0 / 1 == 0, since 1 doesn't have any divisor strictly less than itself. However, I couldn't get an AC (WA4) until I changed the line
if (I == 1) ans = 0
to
if (I == 1) ans = 1.
So, either the statement or the tests are broken.

Edited by author 05.08.2022 19:55

Edited by author 05.08.2022 19:55

Can somebody tell me how they passed test nr. 2 (or give me some good test cases)?

I have a solution in O(N*M*log(N*M)) using suffix array and I can't find the bug.

Thanks

Edited by author 16.09.2010 22:39

Решено.

Edited by author 03.08.2022 20:59

#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main()
{
    int N, sum = 0;
    cin>> N;

    if(N > 0)
    {
        for(int i = 1; i <= N; i++)
        {
            sum = sum + i;
        }
    }
    else if(N <= 0)
    {
        for(int i = N; i <= 1; i++)
        {
            sum = sum + i;
        }
    }

    cout<< sum << endl;

    return 0;
}

a=int(input())
b=0
for i in range(a):
    n,l=map(int, input().split())
    b=b*10+n+l
print('0'*(a-len(str(b))),b, sep='')

Хочется на новой кухне поставить мебель. Я имею в виду не гарнитур, а диван, стулья, стол. Хотелось бы что-нибудь оригинальное и креативное.

Edited by author 01.08.2022 22:29

If you calculate with formulas, then long long is not enough. You can use __int128. You can't read and write it, but you can cast it to and from other integer types.

what about ternary search in this task?



Edited by author 01.10.2020 22:01

Bruteforcing in range [0, 4e7] gives WA9, bruteforcing in range [1e8-4e7,1e8] gives AC

Edited by author 28.07.2022 20:34

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

int main(){
    int n1,n2;
    int a[n1],b[n2];
    cin>>n1;
    for(int k=0;k<n1;k++) cin>>a[k];
    cin>>n2;
    for(int k=0;k<n2;k++) cin>>b[k];
    sort(a,a+n1);
    sort(b,b+n2);
    int i=0,j=n2-1;
    bool ans=false;
    while(i<n1&&j>=0){
        if(a[i]+b[j]==10000){
            ans=true;
            break;
        }
        else if(a[i]+b[j]>10000){
            j--;
        }
        else{
            i++;
        }
    }
    if(ans) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

/*
::::
author:@DEANNOS at CODEFORCES 2022
::::
*/



#include <bits/stdc++.h>
//using policy based stl
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
#define endl "\n"
#define mod 1000000007
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ld  long double
#define ff  first
#define ss  second
#define vs  vector<string>
#define vpll vector<pll>
#define vb  vector<bool>
#define pb push_back
#define bg begin()
#define mp make_pair
#define ed end()
#define gi greater<int> ()
#define srt(v) (sort(all())
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define fo(i,n) for(ll i=0;i<n;i++)
#define Fo(i,k,n) for(ll i=k;i<n;i++)
const int INF = 1000000000;
const int MAX_N = 2e5;



/*
int fastpower(int x, int y, int mod)
{
    int res = 1;
    x = x % mod;
    if (x == 0)
    {
     return 0;
    }
    while (y > 0)
    {
        if (y & 1)
        {
         res = (res*x) % mod;
        }
        y = y>>1;
        x = (x*x) % mod;
    }
    return res;
}
*/

/*
int GCD(int a,int b)
{
 while(b!=0)
 {
  int rem=a%b;
  a=b;
  b=rem;
 }
 return a;
}
*/

ll integer(ll a)
{
    return a >= 0 ? a : -a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    ll ans1 = 1, ans2 = 2, mx = 0;
    ll a;
    cin >> a;
    for (int i = 1; i < n; i++)
    {
        ll b;
        cin >> b;
        if (integr(a - b) > mx)
        {
            mx = integer(a - b);
            ans1 = i;
            ans2 = i + 1;
        }
        a = b;
    }
    cout << ans1 << ans2 << endl;
    return 0;

}

1. Вы пишите:найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте, т.е. количество перекрестков в маршруте должно быть N+1?. в след. абзаце: Все числа x1, …, xk должны быть различны. т.е.  либо маршрут не должен заканчиваться на том же перекресте где начался либо должно быть дополнительное условие Х1=Хк. это принципиальная ошибка в условии.
2. пример который вы привели:
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
4 3
1 2 10
1 3 20
1 4 30
-1
дает результат:
1 3 5 2
No solution.
а куда вы в первом тесте дели перекрестов №4?
3. Исходя из примера маршрут не должен содержать в себе все перекрестки?

Ошибки очевидны. те решения, что вы приняли - частные, случайно полученные.
Уточняйте условия и проверяйте свое решение.

Edited by author 07.11.2014 13:33

Что-то я не совсем понял условие задачи.
"M двусторонних дорог" - т.е. вроде как не ор. граф.
Но пример и решение говорят, о том, что скорее это все таки ор. граф.

1 3 300
3 1 10

Так есть ориентация у ребер или нету?