oj.uz

답안 #369685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
369685 2021-02-22T08:10:20 Z 79brue Meetings (JOI19_meetings) C++14
0 / 100
 156 ms 876 KB 
#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);
            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();
        }

        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));
    }

    struct dat{
        int x, y, z;
        dat(){}
        dat(int _x, int _y, int _z){
            x = min({_x, _y, _z});
            z = max({_x, _y, _z});
            y = _x ^ _y ^ _z ^ x ^ z;
        }
        bool operator<(const dat &r)const{
            return make_pair(x, make_pair(y, z)) < make_pair(r.x, make_pair(r.y, r.z));
        }
    };
    map<dat, int> mp;

    int query(int x, int y, int z){
        if(mp[dat(x, y, z)]) return mp[dat(x, y, z)];
        return mp[dat(x, y, z)] = 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();
        while(true){
            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의 다른 자식과 연결되어 있을 것이다.
                bool done = 0;
                for(auto y: child[c]){
                    if(y == child[c][0]) continue;
                    if(Query(c, down[y], i) != c){
                        c = y;
                        done = 1;
                        break;
                    }
                }
                if(!done){
                    addEdge(c, i);
                    break;
                }
            }
            else if(found[tmp]){
                c = tmp;
            }
            else{ /// 마지막 케이스: 새로운 정점이 발견되었다.
                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], 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);
            }
        }
    }
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Incorrect 1 ms 492 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Incorrect 1 ms 492 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Incorrect 1 ms 492 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 156 ms 876 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -