oj.uz

Submission #16375

# Submission time Handle Problem Language Result Execution time Memory
16375 2015-08-21T17:31:51 Z suhgyuho_william Computer Network (BOI14_network) C++
100 / 100
 157 ms 5204 KB 
#include "network.h"
#include <queue>
using namespace std;

int d[1002],p[1002];
priority_queue <pair<int,int> > q;

void findRoute (int n, int a, int b)
{
    int dist = ping(a,b);
    int i,x,last=b;
    pair<int,int> top;

    d[b]=dist;
    for(i=1;i<=n;i++){
        if(i==a || i==b) continue;
        x=ping(a,i);
        if(x>=dist) continue;
        q.push(make_pair(x,i));
        d[i]=x;
    }
    q.push(make_pair(-1,a));

    while(!q.empty()){
        top=q.top();
        q.pop();
        if(d[last] == top.first) continue;
        if(ping(top.second,last)==0){
            p[d[last]]=last;
            last=top.second;
        }
    }

    for(i=0;i<=dist;i++){
        travelTo(p[i]);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 5204 KB Output is correct
2 Correct 145 ms 5204 KB Output is correct
3 Correct 91 ms 5204 KB Output is correct
4 Correct 111 ms 5204 KB Output is correct
5 Correct 79 ms 5204 KB Output is correct
6 Correct 117 ms 5204 KB Output is correct
7 Correct 0 ms 5204 KB Output is correct
8 Correct 0 ms 5204 KB Output is correct
9 Correct 0 ms 5204 KB Output is correct
10 Correct 0 ms 5204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 5204 KB Output is correct
2 Correct 37 ms 5204 KB Output is correct
3 Correct 128 ms 5204 KB Output is correct
4 Correct 98 ms 5204 KB Output is correct
5 Correct 78 ms 5204 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 5204 KB Output is correct
2 Correct 28 ms 5204 KB Output is correct
3 Correct 125 ms 5204 KB Output is correct
4 Correct 94 ms 5204 KB Output is correct
5 Correct 123 ms 5204 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5204 KB Output is correct
2 Correct 37 ms 5204 KB Output is correct
3 Correct 137 ms 5204 KB Output is correct
4 Correct 108 ms 5204 KB Output is correct
5 Correct 157 ms 5204 KB Output is correct