Submission #369728

#	Time	Username	Problem	Language	Result	Execution time	Memory
369728		79brue	Meetings (JOI19_meetings)	C++14	100 / 100	1192 ms	1860 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace{
    int n;
    vector<int> link[2002];
    bool found[2002];

    vector<int> child[2002];
    int sz[2002], down[2002];
    int par[2002];

    void dfs_sz(int x, int pr=-1){
        sz[x] = 1;
        for(auto &y: link[x]){
            if(y == pr) continue;
            child[x].push_back(y);
            par[y] = x;
            dfs_sz(y, x);
            sz[x] += sz[y];
        }
        for(auto &y: child[x]){
            if(sz[y] > sz[child[x][0]]) swap(y, child[x][0]);
        }
    }

    void dfs_hld(int x){
        down[x] = x;
        for(auto y: child[x]){
            dfs_hld(y);
            if(y == child[x][0]) down[x] = down[y];
        }
    }

    int init(){
        for(int i=0; i<n; i++){
            child[i].clear();
        }
        memset(sz, 0, sizeof(sz));
        memset(down, 0, sizeof(down));
        memset(par, 0, sizeof(par));

        int c = 0;
        dfs_sz(c);
        dfs_hld(c);
        return c;
    }

    void addEdge(int x, int y){
        link[x].push_back(y);
        link[y].push_back(x);
        found[x] = found[y] = 1;
    }
    void delEdge(int x, int y){
        if(find(link[x].begin(), link[x].end(), y) == link[x].end()) exit(1);
        if(find(link[y].begin(), link[y].end(), x) == link[y].end()) exit(1);
        link[x].erase(find(link[x].begin(), link[x].end(), y));
        link[y].erase(find(link[y].begin(), link[y].end(), x));
    }

    map<ll, int> mp;
    int queryCnt = 0;

    int query(int x, int y, int z){
        ll hashCode = ll(x) * 1e12 + ll(y) * 1e6 + ll(z);
        if(mp[hashCode]) return mp[hashCode];

        assert(++queryCnt <= 40000);
        return mp[hashCode] = Query(x, y, z);
    }
}

void Solve(int N){
    n = N;

    found[0] = 1;
    for(int i=1; i<n; i++){ /// 위치를 찾을 정점의 번호
        if(found[i]) continue;
        int c = init();
        int tcnt = 0;
        while(true){
            assert(++tcnt <= 100);
            if(c == down[c]){
                addEdge(c, i);
                break;
            }

            int tmp = query(c, down[c], i);
            if(tmp == down[c]){
                addEdge(down[c], i);
                break;
            }
            else if(tmp == i){
                vector<int> vec;
                vec.push_back(down[c]);
                while(vec.back() != c){
                    vec.push_back(par[vec.back()]);
                }

                int l = 0, r = (int)vec.size()-1;
                while(l < r-1){
                    int p = (l+l+r)/3;
                    int q = (l+r+r)/3;
                    int ret = query(vec[p], vec[q], i);
                    if(ret == i) l = p, r = q;
                    else if(ret == vec[p]) r = p;
                    else l = q;
                }
                delEdge(vec[l], vec[r]);
                addEdge(vec[l], i);
                addEdge(vec[r], i);
                break;
            }
            else if(tmp == c){ /// c의 다른 자식과 연결되어 있을 것이다.
                tmp1:
                bool done = 0;
                for(auto &y: child[c]){
                    if(y == child[c][0]) continue;
                    if(Query(c, down[y], i) != c){
                        down[c] = down[y];
                        swap(y, child[c][0]);
                        done = 1;
                        break;
                    }
                }
                if(!done){
                    addEdge(c, i);
                    break;
                }
            }
            else if(found[tmp]){
                c = tmp;
                goto tmp1;
            }
            else{ /// 마지막 케이스: 새로운 정점이 발견되었다.
                vector<int> vec;
                vec.push_back(down[c]);
                int tcnt = 0;
                while(vec.back() != c){
                    vec.push_back(par[vec.back()]);
                }

                int l = 0, r = (int)vec.size()-1;
                while(l < r-1){
                    int p = (l+l+r)/3;
                    int q = (l+r+r)/3;
                    int ret = query(vec[p], vec[q], tmp);
                    if(ret == tmp) l = p, r = q;
                    else if(ret == vec[p]) r = p;
                    else l = q;
                }
                delEdge(vec[l], vec[r]);
                addEdge(vec[l], tmp);
                addEdge(vec[r], tmp);
                addEdge(tmp, i);
                break;
            }
        }
    }

    for(int i=0; i<n; i++){
        for(auto j: link[i]){
            if(i<j){
//                printf("Bridge %d %d\n", i, j);
                Bridge(i, j);
            }
        }
    }
}

Compilation message (stderr)

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:142:21: warning: unused variable 'tcnt' [-Wunused-variable]
  142 |                 int tcnt = 0;
      |                     ^~~~

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