Submission #16373

#	Time	Username	Problem	Language	Result	Execution time	Memory
16373		suhgyuho_william	Computer Network (BOI14_network)	C++98	100 / 100	167 ms	5204 KiB

network

#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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25