제출 #1193677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193677		omarrrr	City Mapping (NOI18_citymapping)	C++20	0 / 100	11 ms	580 KiB

citymapping

#include "citymapping.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
using namespace std;
bool wchek[1001];
bool vis[1001];
ll linkk[1001];
struct nd{
    ll a,b,w;
};

vector<pair<ll,ll>>v;
vector<nd>res;

void dfs(ll node,ll p){
    vis[node]=1;
    vector<ll>no;
    if(linkk[node]>=3)
        return;
    for(ll i=0;i<v.size();i++){
        if(!vis[v[i].S] && wchek[v[i].S]){
           ll d=get_distance(node,v[i].S);
           if(d<v[i].F){
               dfs(v[i].S,node);
               linkk[node]++;
               res.pb({node,v[i].S,d});
           }else{
               no.pb(v[i].S);
               wchek[v[i].S]=0;
           }
        }
        if(linkk[node]>=3)
            break;
    }
    for(ll x:no){
        wchek[x]=1;
    }
    return;
}

void find_roads(int n, int Q, int A[], int B[], int W[]) {

    for(ll i=1;i<=1000;i++){
        wchek[i]=true;
        linkk[i]=0;
    }
    for(ll i=2;i<=n;i++){
        ll d=get_distance(1, i);
        v.pb({d,i});
    }
    sort(v.begin(),v.end());
    ll c=0;

    for(ll i=0;i<n;i++){
        if(!vis[v[i].S]){
            dfs(v[i].S,1);
            A[c]=1;
            B[c]=v[i].S;
            W[c]=v[i].F;


            c++;
            linkk[1]++;
            linkk[v[i].F]++;

        }
        if(c>=3)
            break;
    }
    for(ll i=0;i<res.size();i++){
        A[c]=res[i].a;
        B[c]=res[i].b;
        W[c]=res[i].w;
    }



    return;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 43