Submission #64614759

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(a) (a).begin(), (a).end()
using ll = long long;
const ll INF32 = 2e9;
const ll INF64 = 4e18;

// インタラクティブな入出力部分を行う.
vector<pair<int,int>> interactive(string &query, int l) {
    cout << query << endl;
    vector<pair<int,int>> mstEdges(l-1);
    rep(i, l-1){
        cin >> mstEdges[i].first >> mstEdges[i].second;
    }
    return mstEdges; 
}

// 都市が存在する可能性がある四角形の座標.
struct square {
    int lx, rx, ly, ry;
};

// 四角形の中心. (lx+rx)/2, (ly+ry)/2.
struct center {
    int x, y;
};

// 辺(道路) 距離, 頂点, 頂点.
struct node {
    int weight, u, v;
};

// Union-Find.
struct UF {
    // par - 親. siz - par[i]=iのとき、その連結成分の個数.
    vector<int> par, siz;
    UF(int N): par(N){
        siz.resize(N);
        for(int i = 0; i < N; i++){
            par[i]=i;
            siz[i]=1;
        }
    }
    // 根を返す.
    int root(int x){
        if(par[x]==x)return x;
        return par[x] = root(par[x]);
    }
    // xの木とyの木を連結.
    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx==ry)return;
        if(siz[rx]<siz[ry]){
            par[rx] = ry;
            siz[ry] += siz[rx]; 
        } else {
            par[ry] = rx;
            siz[rx] += siz[ry];
        }
    }
    // u, vは連結か?
    bool same(int u, int  v){
        return root(u) == root(v);
    }
};

class adv_data {
    public:
    // 入力.
    int N, M, Q, L, W;
    vector<int> G;
    vector<square> cities;
    // 四角形の中心と仮定.
    vector<center> cities_center;
    // ij間の距離(四角形の中心同士).
    vector<vector<int>> dist;
    // 読み取りと前計算.
    void scan(){
        cin >> N >> M >> Q >> L >> W;
        G.resize(M);
        cities.resize(N);
        cities_center.resize(N);
        dist.assign(N, vector(N, 0));
        rep(i, M)cin >> G[i];
        rep(i, N){
            cin >> cities[i].lx >> cities[i].rx >> cities[i].ly >> cities[i].ry;
            cities_center[i].x = (cities[i].lx + cities[i].rx)/2;
            cities_center[i].y = (cities[i].ly + cities[i].ry)/2;
        }
        rep(i, N)rep(j, N){
            int dx = abs(cities_center[i].x-cities_center[j].x);
            int dy = abs(cities_center[i].y-cities_center[j].y);
            dist[i][j] = dx*dx + dy*dy;
        }
    };
};


// 頂点集合を決定する.
void setC(const adv_data &adv, vector<vector<int>> &C, vector<int> &group){
    // 添え字はadv.citiesのindex.
    vector<bool> picked_cities(adv.N);
    // first:adv.Gの昇順ソート. second:adv.Gの対応するindex.
    vector<pair<int,int>> needed_Gidx(adv.M);
    rep(i,adv.M){
        needed_Gidx[i] = {
            adv.G[i],
            i
        };
    }
    sort(all(needed_Gidx),[](auto const &a, auto const &b){
        return a.first > b.first;
    });
    
    // 孤立グループを数える.
    int cntiso = 0;
    if(adv.W<1000)rep(i, adv.G.size())if(adv.G[i]==1)cntiso++;
    vector<pair<int,int>> mindist_idx(adv.N);
    rep(i, adv.N){
        mindist_idx[i].first = *min_element(all(adv.dist[i]));
        mindist_idx[i].second = i;
    }
    sort(all(mindist_idx), [](auto &a, auto &b){
        return a.first > b.first;
    });
    rep(i, cntiso){
        int idx = mindist_idx[i].second;
        picked_cities[idx] = true;
        C[needed_Gidx[adv.M-i-1].second].push_back(idx);
        group[idx] = needed_Gidx[adv.M-i-1].second;
    }

    // first:中心からの距離, second:adv.citiesのindex.
    vector<pair<int,int>> dist_idx(adv.N);
    rep(i,adv.N){
        int dx = abs(adv.cities_center[i].x-5000), dy = abs(adv.cities_center[i].y-5000);
        dist_idx[i] = {dx*dx + dy*dy, i};
    }
    sort(all(dist_idx));
    reverse(all(dist_idx));
    rep(i, adv.M-cntiso){
        // 基準の町. adv.citiesのindexに対応.
        int refcity = -1;
        rep(j, adv.N)if(!(picked_cities[dist_idx[j].second])){
            refcity = dist_idx[j].second;
            picked_cities[refcity] = true;
            C[needed_Gidx[i].second].push_back(refcity);
            group[refcity] = needed_Gidx[i].second;
            break;
        }
        vector<pair<int,int>> disttoref_idx(0);
        // 基準の町から未選択の都市を距離順に並び替え.
        rep(j, adv.N)if(!(picked_cities[j])){
            disttoref_idx.push_back({
                adv.dist[refcity][j],
                j
            });
        }
        sort(all(disttoref_idx));
        // 上位needed個をpickしてCに入れる.
        rep(j, needed_Gidx[i].first-1){//-1はrefcity分.
            int pick = disttoref_idx[j].second;
            picked_cities[pick] = true;
            C[needed_Gidx[i].second].push_back(pick);
            group[pick] = needed_Gidx[i].second;
        }
    }
    return;
}

// 誤差は無視し最小全域木を前計算.
vector<pair<int, int>> MST(const adv_data &adv, vector<int> &C){
    vector<node> nodelist(0);
    for(auto p: C)for(auto q: C){
        if(p>=q)continue;
        node nodepq;
        nodepq.u = p;
        nodepq.v = q;
        nodepq.weight = adv.dist[p][q];
        nodelist.push_back(nodepq);
    }
    // 昇順に.
    sort(all(nodelist), [](auto const &a, auto const &b){
        return a.weight < b.weight;
    });
    //indexはadv.citiesの添え字対応.
    UF uf(adv.N);
    // クラスカル法.
    // 戻り値-C.size()-1本の辺.
    vector<pair<int,int>> edge(C.size()-1);
    int cnt = 0;
    rep(i, nodelist.size()){
        int u = nodelist[i].u, v = nodelist[i].v;
        if(!uf.same(u, v)){
            uf.unite(u, v);
            edge[cnt] = {u,v};
            cnt++;
        }
    }
    return edge;
}

// 答えを出力.
void printAns(const vector<vector<int>> &C, const vector<vector<pair<int,int>>> edge){
    cout << '!' << endl;
    rep(i, C.size()){
        string strC = "";
        rep(j, C[i].size()){
            strC += to_string(C[i][j]);
            if(j==C[i].size()-1);
            else strC += " ";
        }
        cout << strC << endl;
        rep(j, edge[i].size()){
            cout << edge[i][j].first << " " << edge[i][j].second << endl;
        }
    }
}

// 出力する文字列に変換.
string formatQueryStr (set<int> &st){
    string outPut = "? ";
    outPut += to_string(st.size());
    for(auto p: st)outPut += " " + to_string(p);
    return outPut;
}

// 占い結果をもとに置き換える.
void replace(vector<pair<int,int>> &edge, set<int> &st, vector<set<int>> &adj_set, string &output, adv_data &adv) {
    vector<pair<int, int>> ans = interactive(output, st.size());
    // adj_setからもともとの辺を削除.
    for(auto &p : edge){
        if(st.count(p.first)&&st.count(p.second)){
            adj_set[p.first].erase(p.second);
            adj_set[p.second].erase(p.first);
        }
    }
    // edgeを置き換えadj_setに新しい辺を追加.
    int idx = 0;
    for(auto &p : edge){
        if(st.count(p.first)&&st.count(p.second)){
            p.first = ans[idx].first;
            p.second = ans[idx].second;
            adj_set[p.first].insert(p.second);
            adj_set[p.second].insert(p.first);
            idx++;
        }
    }
    return;
}

// 占う関数.
bool query(adv_data &adv, vector<vector<pair<int,int>>> &edge, vector<vector<int>> &C, vector<int> &group, vector<set<int>> &adj_set, vector<bool> &done , set<set<int>> &usedst){
    int root = rand() % adv.N;
    // 木の番号. C/G/doneの添え字に対応.
    int Cidx = group[root];
    // 頂点数が 3 未満は占う意味がない.
    if(C[Cidx].size()<3){
        done[Cidx] = true;
        return false;
    }
    // 頂点数が L 以下は1度占えば十分.
    else if(C[Cidx].size()<=adv.L){
        if(done[Cidx])return false;
        else done[Cidx] = true;
    }
    // 隣接頂点をBFSし 部分木を得る.
    // 部分木の頂点番号のリスト.
    set<int> st;
        queue<int> q; vector<bool> seen(adv.N, false);
        q.push(root);
        seen[root] = true;
        while(!(q.empty())&&st.size()<adv.L){
            auto t = q.front(); q.pop();
            int nw = t;
            st.insert(nw);
            for(auto p : adj_set[nw]){
                if(seen[p])continue;
                seen[p] = true;
                q.push(p);
            }
        }
    // adv.M <= 2 だと破滅するのでusedstで分岐.
    if(adv.M > 2 && usedst.count(st))return false;
    else if(adv.M > 2)usedst.insert(st);
    string query = formatQueryStr(st);
    // edgeを置き換え.
    replace(edge[Cidx], st, adj_set, query,adv);
    return true;
}

void HC(adv_data &adv,vector<vector<pair<int,int>>> &edge, vector<vector<int>> &C, vector<set<int>> &adj_set, vector<int> &group){
    // 候補として、次数0~1の都市を列挙.
    auto startTime = chrono::high_resolution_clock::now();
    double elapsed = 0;
    vector<int> cand(0);
    rep(i, adv.N)if(adj_set[i].size()<=1)cand.push_back(i);
    while(elapsed < 50 * sqrt(adv.M)){
        auto currentTime = chrono::high_resolution_clock::now();
        elapsed = chrono::duration_cast<chrono::milliseconds>(currentTime - startTime).count();
        int u = rand()%cand.size(), v = rand()%cand.size();
        u = cand[u]; v = cand[v];
        // 孤立都市同士.
        if(adj_set[u].size()==0&&adj_set[v].size()==0)continue;
        // 既に同じ頂点.
        else if(group[u]==group[v])continue;
        else if(adj_set[u].size()==0){
            int par = *adj_set[v].begin();
            if(adv.dist[par][u]>adv.dist[par][v])continue;
        }
        else if(adj_set[v].size()==0){
            int par = *adj_set[u].begin();
            if(adv.dist[par][v]>adv.dist[par][u])continue;
        }
        else {
            int par_u = *adj_set[u].begin(), par_v = *adj_set[v].begin();
            if(adv.dist[par_u][u]+adv.dist[par_v][v]<adv.dist[par_u][v]+adv.dist[par_v][u])continue;
        }
        // Edge更新.
        for(auto &p: edge[group[u]]){
            if(p.first==u)p.first = v;
            if(p.second==u)p.second = v;
        }
        for(auto &p: edge[group[v]]){
            if(p.first==v)p.first = u;
            if(p.second==v)p.second = u;
        }
        // C更新.
        for(auto &p: C[group[u]]){
            if(p==u)p = v;
        }
        for(auto &p: C[group[v]]){
            if(p==v)p = u;
        }
        // adj_set更新.
        swap(adj_set[u], adj_set[v]);
        for(auto p: adj_set[u]){
            adj_set[p].erase(v);
            adj_set[p].insert(u);
        }
        for(auto p: adj_set[v]){
            adj_set[p].erase(u);
            adj_set[p].insert(v);
        }
        // group更新.
        swap(group[u], group[v]);
    }
}

int main() {
    auto startTime = chrono::high_resolution_clock::now();
    double elapsed = 0;
    srand((unsigned int)time(NULL));
    adv_data adv;
    // 1. 事前情報を読み込む.
    adv.scan();
    // 2. 頂点集合.
    vector<vector<int>> C(adv.M,vector(0,0));
    vector<int> group(adv.N);
    setC(adv, C, group);
    // 3. MSTを構築.
    vector<vector<pair<int,int>>> edge(adv.M, vector<pair<int,int>>(0));
    rep(i, adv.M)edge[i] = MST(adv, C[i]);
    // 3.1 vector<set<int>>.
    vector<set<int>> adj_set(adv.N);
    rep(i, edge.size())rep(j, edge[i].size()){
        int u = edge[i][j].first, v = edge[i][j].second;
        adj_set[u].insert(v);
        adj_set[v].insert(u);
    }
    // 4. 山登り法でCを修正.(100ms).
    HC(adv, edge, C, adj_set, group);
    // 5. 占い.
        // 3頂点~L頂点の木はクエリ1回のみ.
        vector done(adv.M, false);
        // 2回同じ出力をしないように
        set<set<int>> usedst;

    int cnt = 0; 
    bool ok = true;// 無限ループ阻止.
    while(cnt < adv.Q && ok && elapsed < 1900){
        cnt += query(adv, edge, C, group, adj_set, done, usedst);
        ok = false;
        rep(i, adv.M)ok = ok || !(done[i]);
        auto currentTime = chrono::high_resolution_clock::now();
        elapsed = chrono::duration_cast<chrono::milliseconds>(currentTime - startTime).count();
    }
    // 6. 出力.
    printAns(C, edge);
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void printAns(const std::vector<std::vector<int> >&, std::vector<std::vector<std::pair<int, int> > >)’:
Main.cpp:212:17: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  212 |             if(j==C[i].size()-1);
      |                ~^~~~~~~~~~~~~~~
Main.cpp: In function ‘void replace(std::vector<std::pair<int, int> >&, std::set<int>&, std::vector<std::set<int> >&, std::string&, adv_data&)’:
Main.cpp:231:110: warning: unused parameter ‘adv’ [-Wunused-parameter]
  231 | void replace(vector<pair<int,int>> &edge, set<int> &st, vector<set<int>> &adj_set, string &output, adv_data &adv) {
      |                                                                                                    ~~~~~~~~~~^~~
Main.cpp: In function ‘bool query(adv_data&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<std::set<int> >&, std::vector<bool>&, std::set<std::set<int> >&)’:
Main.cpp:265:27: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  265 |     else if(C[Cidx].size()<=adv.L){
      |             ~~~~~~~~~~~~~~^~~~~~~
Main.cpp:275:38: warning: comparison of integer expressions of different signedness: ‘std::set<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  275 |         while(!(q.empty())&&st.size()<adv.L){
      |                             ~~~~~~~~~^~~~~~

Judge Result