Submission #706941

#	Time	Username	Problem	Language	Result	Execution time	Memory
706941		minhnhatnoe	ICC (CEOI16_icc)	C++17	100 / 100	110 ms	640 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct dsu{
    int c_cnt;
    vector<int> p;
    vector<vector<int>> c;
    dsu(int n): c(n), p(n, -1), c_cnt(n){
        for (int i=0; i<n; i++)
            c[i].push_back(i);
    }
    int find(int v){
        if (p[v] < 0) return v;
        return p[v] = find(p[v]);
    }
    void merge(int a, int b){
        a = find(a), b = find(b);
        if (a == b) return;
        if (-p[a] < -p[b]) swap(a, b);
        p[a] += p[b]; p[b] = a;
        c[a].insert(c[a].end(), c[b].begin(), c[b].end());
        c[b].clear();
        c_cnt--;
    }
};
int raw_query(vector<int> l, vector<int> r){
    for (int i=0; i<l.size(); i++) l[i]++;
    for (int i=0; i<r.size(); i++) r[i]++;
    return query(l.size(), r.size(), l.data(), r.data());
}
int cu_query(dsu &g, vector<int> l, vector<int> r){
    if (l.size() == 0 || r.size() == 0) return false;
    vector<int> left, right;
    for (int x: l)
        left.insert(left.end(), g.c[x].begin(), g.c[x].end());
    for (int x: r)
        right.insert(right.end(), g.c[x].begin(), g.c[x].end());
    return raw_query(left, right);
}
void distrib(vector<int> c, vector<int> &left, vector<int> &right){
    auto mid = c.begin() + c.size()/2;
    left.insert(left.end(), c.begin(), mid);
    right.insert(right.end(), mid, c.end());
}
vector<vector<int>> solve1(dsu &g){
    vector<vector<int>> c(1);
    for (int i=0; i<g.p.size(); i++)
        if (g.find(i) == i)
            c[0].push_back(i);

    while (true){
        vector<int> left, right;
        for (int i=0; i<c.size(); i++)
            distrib(c[i], left, right);

        if (cu_query(g, left, right)) break;
        for (int i=c.size()-1; i>=0; i--){
            auto mid = c[i].begin() + c[i].size()/2;
            c.emplace_back(mid, c[i].end());
            c[i].resize(c[i].size()/2);
        }
        vector<vector<int>> nc;
        for (int i=0; i<c.size(); i++){
            if (c[i].size() == 1) continue;
            nc.push_back(move(c[i]));
        }
        c = move(nc);
    }
    return c;
}
vector<int> solve2(dsu &g, vector<vector<int>> c){
    int bl = 0, br=c.size()-1;
    while (bl < br){
        int bm = (bl+br)>>1;
        vector<int> left, right;
        for (int i=0; i<=bm; i++)
            distrib(c[i], left, right);
        if (cu_query(g, left, right))
            br = bm;
        else bl = bm+1;
    }
    return c[bl];
}
pair<int, int> solve3(dsu &g, vector<int> left, vector<int> right){
    vector<int> l, r;
    for (int x: left) l.insert(l.end(), g.c[x].begin(), g.c[x].end());
    for (int x: right) r.insert(r.end(), g.c[x].begin(), g.c[x].end());

    while (true){
        if (l.size() == 1 && r.size() == 1) return {l[0], r[0]};
        if (r.size() == 1) swap(l, r);
        vector<int> r1, r2;
        distrib(r, r1, r2);
        if (raw_query(l, r1)) r = r1;
        else r = r2;
    }
}
void run(int N){
    dsu g(N);
    for (int i=0; i<N; i++){
        vector<vector<int>> c = solve1(g);
        vector<int> cbl = solve2(g, c);
        auto mid = cbl.begin() + cbl.size()/2;
        vector<int> left(cbl.begin(), mid), right(mid, cbl.end());
        pair<int, int> result = solve3(g, left, right);
        g.merge(result.first, result.second);
        setRoad(result.first+1, result.second+1);
    }
}

Compilation message (stderr)

icc.cpp: In constructor 'dsu::dsu(int)':
icc.cpp:9:25: warning: 'dsu::c' will be initialized after [-Wreorder]
    9 |     vector<vector<int>> c;
      |                         ^
icc.cpp:8:17: warning:   'std::vector<int> dsu::p' [-Wreorder]
    8 |     vector<int> p;
      |                 ^
icc.cpp:10:5: warning:   when initialized here [-Wreorder]
   10 |     dsu(int n): c(n), p(n, -1), c_cnt(n){
      |     ^~~
icc.cpp:8:17: warning: 'dsu::p' will be initialized after [-Wreorder]
    8 |     vector<int> p;
      |                 ^
icc.cpp:7:9: warning:   'int dsu::c_cnt' [-Wreorder]
    7 |     int c_cnt;
      |         ^~~~~
icc.cpp:10:5: warning:   when initialized here [-Wreorder]
   10 |     dsu(int n): c(n), p(n, -1), c_cnt(n){
      |     ^~~
icc.cpp: In function 'int raw_query(std::vector<int>, std::vector<int>)':
icc.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0; i<l.size(); i++) l[i]++;
      |                   ~^~~~~~~~~
icc.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i=0; i<r.size(); i++) r[i]++;
      |                   ~^~~~~~~~~
icc.cpp: In function 'std::vector<std::vector<int> > solve1(dsu&)':
icc.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i=0; i<g.p.size(); i++)
      |                   ~^~~~~~~~~~~
icc.cpp:55:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i=0; i<c.size(); i++)
      |                       ~^~~~~~~~~
icc.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i=0; i<c.size(); i++){
      |                       ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10