oj.uz

Submission #34554

# Submission time Handle Problem Language Result Execution time Memory
34554 2017-11-12T11:15:09 Z Extazy Computer Network (BOI14_network) C++14
100 / 100
 146 ms 6036 KB 
#include <bits/stdc++.h>
#include "network.h"

#define endl '\n'

using namespace std;

const int N = 1024;

int n,a,b;
int da[N],db[N];
int min_dist;
int shortest,path[N],path_sz;
bool used[N];
vector < int > v[N];

/*void travelTo(int x) {
}

int ping(int a, int b) {
    
}*/

int ask(int a, int b) {
    if(a==b) return 0;
    return 1+ping(a,b);
}

bool cmp(int a, int b) {
    return da[a]<da[b];
}

void findRoute(int N, int A, int B) {
    int i,j;
    
    n=N;
    a=A;
    b=B;

    shortest=ask(a,b);
    da[a]=0;
    da[b]=shortest;
    db[a]=shortest;
    db[b]=0;
    path_sz=0;

    for(i=0;i<=n;i++) v[i].clear();

    for(i=1;i<=n;i++) if(i!=a && i!=b) {
        db[i]=ask(i,b);
        v[db[i]].push_back(i);
    }

    int where=a;
    for(j=shortest-1;j>=1;j--) {
        for(i=0;i<(int)(v[j].size());i++) {
            int curr=v[j][i];
            da[curr]=ask(curr,where);
            if(da[curr]==1) {
                travelTo(curr);
                where=curr;
                break;
            }
        }
    }
    travelTo(b);
}

/*int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    return 0;
}*/

Compilation message

grader.c: In function 'int main()':
grader.c:48:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d%d%d%d", &N, &a, &b, &M);
                                       ^
grader.c:51:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &distance[u][v]);
                                         ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 6036 KB Output is correct
2 Correct 109 ms 6036 KB Output is correct
3 Correct 103 ms 6036 KB Output is correct
4 Correct 103 ms 6036 KB Output is correct
5 Correct 146 ms 6036 KB Output is correct
6 Correct 129 ms 6036 KB Output is correct
7 Correct 0 ms 6036 KB Output is correct
8 Correct 0 ms 6036 KB Output is correct
9 Correct 0 ms 6036 KB Output is correct
10 Correct 0 ms 6036 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 6036 KB Output is correct
2 Correct 23 ms 6036 KB Output is correct
3 Correct 126 ms 6036 KB Output is correct
4 Correct 89 ms 6036 KB Output is correct
5 Correct 106 ms 6036 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 6036 KB Output is correct
2 Correct 26 ms 6036 KB Output is correct
3 Correct 93 ms 6036 KB Output is correct
4 Correct 99 ms 6036 KB Output is correct
5 Correct 119 ms 6036 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 6036 KB Output is correct
2 Correct 39 ms 6036 KB Output is correct
3 Correct 99 ms 6036 KB Output is correct
4 Correct 83 ms 6036 KB Output is correct
5 Correct 116 ms 6036 KB Output is correct