oj.uz

Submission #16373

# Submission time Handle Problem Language Result Execution time Memory
16373 2015-08-21T17:29:39 Z suhgyuho_william Computer Network (BOI14_network) C++
100 / 100
 167 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]);
    }
}

// m = 3n 일 때

/*#include "network.h"
#include <map>
using namespace std;

map<int,int> mp;
map<int,int>::iterator it,t1,t2;
bool check[1002];

void findRoute (int n, int a, int b)
{
    int dist = ping(a, b);
    int i,x,y,t;

    mp[dist+1]=b;
    check[dist+1]=1;
    mp[0]=a;
    check[0]=1;

    for(i=1;i<=n;i++){
        if(i==a || i==b) continue;
        x=ping(a,i);
        if(x >= dist) continue;
        if(check[x+1]) continue;
        mp[x+1]=i;
        it=mp.find(x+1);

        t1=it;
        t1--;
        t=ping(t1->second,i);

        t2=it;
        t2++;
        y=ping(i,t2->second);
        if(t+y+2 != t2->first - t1->first){
            mp.erase(it);
        }else{
            check[x+1]=1;
        }
    }

    for(it=(++mp.begin()); it!=mp.end(); it++){
        travelTo(it->second);
    }
}

*/

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 5204 KB Output is correct
2 Correct 110 ms 5204 KB Output is correct
3 Correct 120 ms 5204 KB Output is correct
4 Correct 114 ms 5204 KB Output is correct
5 Correct 121 ms 5204 KB Output is correct
6 Correct 93 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 70 ms 5204 KB Output is correct
2 Correct 30 ms 5204 KB Output is correct
3 Correct 146 ms 5204 KB Output is correct
4 Correct 111 ms 5204 KB Output is correct
5 Correct 123 ms 5204 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5204 KB Output is correct
2 Correct 25 ms 5204 KB Output is correct
3 Correct 125 ms 5204 KB Output is correct
4 Correct 113 ms 5204 KB Output is correct
5 Correct 127 ms 5204 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 5204 KB Output is correct
2 Correct 26 ms 5204 KB Output is correct
3 Correct 129 ms 5204 KB Output is correct
4 Correct 65 ms 5204 KB Output is correct
5 Correct 138 ms 5204 KB Output is correct