Submission #414932

#	Time	Username	Problem	Language	Result	Execution time	Memory
414932		Pro_ktmr	Meetings (JOI19_meetings)	C++17	100 / 100	895 ms	2276 KiB

meetings

#include "meetings.h"

#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
template<class T> bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
constexpr int dy[4]={ -1,0,1,0 };
constexpr int dx[4]={ 0,-1,0,1 };

namespace{
    map<pair<pair<int,int>,int>,int> memo;
    int query(int u, int v, int w){
        if(u > v) swap(u, v);
        if(v > w) swap(v, w);
        if(u > v) swap(u, v);
        if(u == v) return v;
        if(v == w) return v;
        if(memo.count({{u,v},w})) return memo[{{u,v},w}];
        return memo[{{u,v},w}] = Query(u, v, w);
    }
    vector<int> e[2000];
    bool used[2000];
    int sz;
    int CentroidDecomposition(int n, int p){ // find one centroid
        int ma = 0;
        int sum = 1;
        rep(i, e[n].size()){
            if(e[n][i] == p || used[e[n][i]]) continue;
            int ret = CentroidDecomposition(e[n][i], n);
            if(ret <= 0) return ret;
            chmax(ma, ret);
            sum += ret;
        }
        if(ma <= sz / 2 && sz - sum <= sz / 2) return -n;
        return sum;
    }
    int size(int n, int p){
        int sum = 1;
        rep(i, e[n].size()){
            if(e[n][i] == p || used[e[n][i]]) continue;
            sum += size(e[n][i], n);
        }
        return sum;
    }
    void fill(int n, int p){
        used[n] = true;
        sz--;
        rep(i, e[n].size()){
            if(e[n][i] == p || used[e[n][i]]) continue;
            fill(e[n][i], n);
        }
    }
    void erase(vector<int> &v, int x){
        rep(i, v.size()){
            if(v[i] == x){
                v.erase(v.begin()+i);
                break;
            }
        }
    }
};

void Solve(int N) {
    vector<int> v;
    rep(i, N) v.pb(i);
    random_device seed_gen;
    mt19937 engine(seed_gen());
    shuffle(all(v), engine);

    e[v[0]].pb(v[1]);
    e[v[1]].pb(v[0]);

    for(int i=2; i<N; i++){
        sz = i;
        memset(used, false, sizeof(used));
        bool flg = true;
        int root = v[0];
        while(flg){
            int u = -CentroidDecomposition(root, -1); // O(N^2 log N)
            assert(u >= 0);
            vector<pair<int,int>> tmp;
            rep(j, e[u].size()){
                if(used[e[u][j]]) continue;
                tmp.pb({size(e[u][j], u), e[u][j]});
            }
            sort(all(tmp));
            reverse(all(tmp));
            if(tmp.size() == 0){
                e[u].pb(v[i]);
                e[v[i]].pb(u);
                break;
            }
            bool ok = false;
            for(int j=0; j<tmp.size(); j+=2){
                if(j+1 == tmp.size()){
                    if(!ok){
                        int ret = query(u, tmp[j].second, v[i]);
                        if(ret == v[i]){
                            erase(e[u], tmp[j].second);
                            erase(e[tmp[j].second], u);
                            e[u].pb(v[i]);
                            e[tmp[j].second].pb(v[i]);
                            e[v[i]].pb(u);
                            e[v[i]].pb(tmp[j].second);
                            ok = true;
                            flg = false;
                            break;
                        }
                        if(ret == tmp[j].second){
                            ok = true;
                            root = tmp[j].second;
                            continue;
                        }
                        if(ret != u){
                            erase(e[u], tmp[j].second);
                            erase(e[tmp[j].second], u);
                            e[u].pb(ret);
                            e[tmp[j].second].pb(ret);
                            e[ret].pb(u);
                            e[ret].pb(tmp[j].second);
                            ok = true;
                            flg = false;
                            for(int k=i+1; k<v.size(); k++){
                                if(v[k] == ret) swap(v[k], v[i]);
                            }
                            break;
                        }
                    }
                    fill(tmp[j].second, u);
                }
                else{
                    if(!ok){
                        int ret = query(tmp[j].second, tmp[j+1].second, v[i]);
                        if(ret == v[i]){
                            int ret2 = query(u, tmp[j].second, v[i]);
                            if(ret2 == v[i]){
                                erase(e[u], tmp[j].second);
                                erase(e[tmp[j].second], u);
                                e[u].pb(v[i]);
                                e[tmp[j].second].pb(v[i]);
                                e[v[i]].pb(u);
                                e[v[i]].pb(tmp[j].second);
                            }
                            else{
                                erase(e[u], tmp[j+1].second);
                                erase(e[tmp[j+1].second], u);
                                e[u].pb(v[i]);
                                e[tmp[j+1].second].pb(v[i]);
                                e[v[i]].pb(u);
                                e[v[i]].pb(tmp[j+1].second);
                            }
                            ok = true;
                            flg = false;
                            break;
                        }
                        if(ret == tmp[j].second){
                            ok = true;
                            root = tmp[j].second;
                            fill(tmp[j+1].second, u);
                            continue;
                        }
                        if(ret == tmp[j+1].second){
                            ok = true;
                            root = tmp[j+1].second;
                            fill(tmp[j].second, u);
                            continue;
                        }
                        if(ret != u){
                            int ret2 = query(u, tmp[j].second, ret);
                            if(ret2 == ret){
                                erase(e[u], tmp[j].second);
                                erase(e[tmp[j].second], u);
                                e[u].pb(ret);
                                e[tmp[j].second].pb(ret);
                                e[ret].pb(u);
                                e[ret].pb(tmp[j].second);
                            }
                            else{
                                erase(e[u], tmp[j+1].second);
                                erase(e[tmp[j+1].second], u);
                                e[u].pb(ret);
                                e[tmp[j+1].second].pb(ret);
                                e[ret].pb(u);
                                e[ret].pb(tmp[j+1].second);
                            }
                            for(int k=i+1; k<v.size(); k++){
                                if(v[k] == ret) swap(v[k], v[i]);
                            }
                            ok = true;
                            flg = false;
                            break;
                        }
                        fill(tmp[j].second, u);
                        fill(tmp[j+1].second, u);
                    }
                    else{
                        fill(tmp[j].second, u);
                        fill(tmp[j+1].second, u);
                    }
                }
                
            }
            if(!ok){
                e[u].pb(v[i]);
                e[v[i]].pb(u);
                break;
            }
            used[u] = true;
            sz--;
        }
        
        /*rep(j, N){
            cout << j << ":";
            rep(k, e[j].size()){
                cout << " " << e[j][k];
            }
            cout << endl;
        }*/
    }
    
    vector<pair<int,int>> ans;
    rep(i, N){
        rep(j, e[i].size()){
            ans.pb({min(i, e[i][j]), max(i, e[i][j])});
        }
    }
    sort(all(ans));
    ans.erase(unique(all(ans)), ans.end());
    rep(i, N-1){
        Bridge(ans[i].first, ans[i].second);
    }
}

Compilation message (stderr)

meetings.cpp: In function 'int {anonymous}::CentroidDecomposition(int, int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
meetings.cpp:37:9: note: in expansion of macro 'rep'
   37 |         rep(i, e[n].size()){
      |         ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
meetings.cpp:37:9: note: in expansion of macro 'rep'
   37 |         rep(i, e[n].size()){
      |         ^~~
meetings.cpp: In function 'int {anonymous}::size(int, int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
meetings.cpp:49:9: note: in expansion of macro 'rep'
   49 |         rep(i, e[n].size()){
      |         ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
meetings.cpp:49:9: note: in expansion of macro 'rep'
   49 |         rep(i, e[n].size()){
      |         ^~~
meetings.cpp: In function 'void {anonymous}::fill(int, int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
meetings.cpp:58:9: note: in expansion of macro 'rep'
   58 |         rep(i, e[n].size()){
      |         ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
meetings.cpp:58:9: note: in expansion of macro 'rep'
   58 |         rep(i, e[n].size()){
      |         ^~~
meetings.cpp: In function 'void {anonymous}::erase(std::vector<int>&, int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
meetings.cpp:64:9: note: in expansion of macro 'rep'
   64 |         rep(i, v.size()){
      |         ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
meetings.cpp:64:9: note: in expansion of macro 'rep'
   64 |         rep(i, v.size()){
      |         ^~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
meetings.cpp:75:5: note: in expansion of macro 'rep'
   75 |     rep(i, N) v.pb(i);
      |     ^~~
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
meetings.cpp:92:13: note: in expansion of macro 'rep'
   92 |             rep(j, e[u].size()){
      |             ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
meetings.cpp:92:13: note: in expansion of macro 'rep'
   92 |             rep(j, e[u].size()){
      |             ^~~
meetings.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(int j=0; j<tmp.size(); j+=2){
      |                          ~^~~~~~~~~~~
meetings.cpp:105:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |                 if(j+1 == tmp.size()){
      |                    ~~~~^~~~~~~~~~~~~
meetings.cpp:133:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |                             for(int k=i+1; k<v.size(); k++){
      |                                            ~^~~~~~~~~
meetings.cpp:196:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |                             for(int k=i+1; k<v.size(); k++){
      |                                            ~^~~~~~~~~
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
meetings.cpp:232:5: note: in expansion of macro 'rep'
  232 |     rep(i, N){
      |     ^~~
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
meetings.cpp:233:9: note: in expansion of macro 'rep'
  233 |         rep(j, e[i].size()){
      |         ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
meetings.cpp:233:9: note: in expansion of macro 'rep'
  233 |         rep(j, e[i].size()){
      |         ^~~
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
meetings.cpp:239:5: note: in expansion of macro 'rep'
  239 |     rep(i, N-1){
      |     ^~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71