Submission #30684

#	Time	Username	Problem	Language	Result	Execution time	Memory
30684		jenkhai	ICC (CEOI16_icc)	C++14	0 / 100	323 ms	18952 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef vector<int> vi;
const int MAXN = 110;
struct UnionFind{
    vi p, rank;
    vector<vi> members;
    int N;
    UnionFind(int _N) {
        N = _N;
        p.assign(N+1, 0);
        rank.assign(N+1, 0);
        members.assign(N+1, vi());
        for(int i=1;i<=N;i++) {
            p[i] = i;
            members[i].push_back(i);
        }
    }
    UnionFind() {}

    int root(int u) {
        return (p[u]==u)?u:p[u]=root(p[u]);
    }
    
    void merge(int i, int j) {
        int b = root(i), s = root(j);
        if(rank[b] < rank[s]) swap(b, s);
        if(rank[b]==rank[s]) rank[b]++;
        for(int i=0;i<members[s].size();i++) {
            members[b].push_back(members[s][i]);
        }
        p[s] = b;
    }
};

UnionFind UF;

pair<int, int> solve(queue<int> q1, queue<int> q2) {
    //q1 has same size s q2, or 1 bigger than q2

    //rebalance queues and build a and b 
    while(q2.size()>q1.size()) {
        q1.push(q2.front()); q2.pop();
    }

    while(q1.size()>q2.size()+1) {
        q2.push(q1.front()); q1.pop();
    }
    if(q1.size() == 0 || q2.size() == 0) return make_pair(-1, -1);

    bool last_query = (q1.size()==1)&&(q2.size()==1);

    stack<int> s1, s2;
    int size_a=0, size_b=0, a[MAXN], b[MAXN];
    //printf("%d %d\n", q1.size(), q2.size());
    
    while(!q1.empty()) {
        int u = q1.front(); q1.pop();   
        for(int i=0;i<UF.members[u].size();i++) {
            a[size_a++] = UF.members[u][i];
            //printf("%d ", UF.members[u][i]);
        } //printf("\n");
        s1.push(u);
    }
    //printf("===\n");
    while(!q2.empty()) {
        int u = q2.front(); q2.pop();
        for(int i=0;i<UF.members[u].size();i++) {
            b[size_b++] = UF.members[u][i];
            //printf("%d ", UF.members[u][i]);
        } //printf("\n");
        s2.push(u);
    }

    //case if two representatives left
    if(last_query) {
        if(query(size_a, size_b, a, b)) return make_pair(s1.top(), s2.top());
        else return make_pair(-1, -1);
    }
    //otherwise recurse 
    pair<int, int> ret;
    if(query(size_a, size_b, a, b)) {
        while(!s2.empty()) {
            q2.push(s2.top()); s2.pop();
        }
        int siz = s1.size()/2;
        while(s1.size()>siz) {
            q1.push(s1.top()); s1.pop();
        }
        ret = solve(q1, q2);
        if(ret.first != -1) return ret;

        while(!s1.empty()) {
            q1.push(s1.top()); s1.pop();
        }
        ret = solve(q1, q2);
        if(ret.first != -1) return ret;
    } else {
        while(!s1.empty()) {
            q1.push(s1.top()); s1.pop();
        }
        ret = solve(q1, queue<int>());
        if(ret.first != -1) return ret;
        while(!s2.empty()) {
            q2.push(s2.top()); s2.pop();
        }
        ret = solve(q2, queue<int>());
        if(ret.first != -1) return ret;
    }
    //printf("===END===\n");
    return make_pair(-1, -1);
}

pair<int, int> solve2(queue<int> q1, queue<int> q2) {
    //q1 has same size s q2, or 1 bigger than q2

    //rebalance queues and build a and b 
    while(q2.size()>q1.size()) {
        q1.push(q2.front()); q2.pop();
    }

    while(q1.size()>q2.size()+1) {
        q2.push(q1.front()); q1.pop();
    }
    if(q1.size() == 0 || q2.size() == 0) return make_pair(-1, -1);

    bool last_query = (q1.size()==1)&&(q2.size()==1);

    stack<int> s1, s2;
    int size_a=0, size_b=0, a[MAXN], b[MAXN];
    //printf("%d %d\n", q1.size(), q2.size());
    
    while(!q1.empty()) {
        int u = q1.front(); q1.pop();   
        a[size_a++] = u;
        s1.push(u);
    }
    //printf("===\n");
    while(!q2.empty()) {
        int u = q2.front(); q2.pop();
        b[size_b++] = u;
        s2.push(u);
    }

    //case if two nodes left
    if(last_query) {
        if(query(size_a, size_b, a, b)) return make_pair(s1.top(), s2.top());
        else return make_pair(-1, -1);
    }
    //otherwise recurse 
    pair<int, int> ret;
    while(!s2.empty()) {
        q2.push(s2.top()); s2.pop();
    }
    int siz = s1.size()/2;
    while(s1.size()>siz) {
        q1.push(s1.top()); s1.pop();
    }
    ret = solve2(q1, q2);
    if(ret.first != -1) return ret;

    while(!s1.empty()) {
        q1.push(s1.top()); s1.pop();
    }
    ret = solve2(q1, q2);
    if(ret.first != -1) return ret;
   
    //printf("===END===\n");
    return make_pair(-1, -1);
}

bool test(int x, int y) {
    int a[] = {x};
    int b[] = {y};
    return query(1, 1, a, b);
}

void print() {
    printf("TRUE EDGES:\n");
    int N = 15;
    for(int i=1;i<=N;i++) {
        for(int j=i+1;j<=N;j++) {
            if(test(i, j)) printf("%d %d\n", i, j);
        }
    }
    printf("===THE END===\n");
}

void run(int N) {   
    UF=UnionFind(N);
    //cout << N << endl;
    int times = N-1;
    //print();
    while(times--) {
        queue<int> q1, q2;
        for(int i=1;i<=N;i++) {
            if(UF.p[i] == i) {
               if(q1.size()>q2.size()) q2.push(i);
               else q1.push(i);
            }
        }
        pair<int, int> reps = solve(q1,q2);
        queue<int> qq1, qq2;
        for(int i=0;i<UF.members[reps.first].size();i++) {
            qq1.push(UF.members[reps.first][i]);
        } 
        for(int i=0;i<UF.members[reps.second].size();i++) {
            qq2.push(UF.members[reps.second][i]);
        } 
        pair<int, int> ans = solve2(qq1, qq2);
        UF.merge(reps.first, reps.second);
        //printf("%d: reps:%d %d ans:(%d->%d)\n", q1.size()+q2.size(), reps.first, reps.second, ans.first, ans.second);
    
        setRoad(ans.first, ans.second); 
    }
}

Compilation message (stderr)

icc.cpp: In member function 'void UnionFind::merge(int, int)':
icc.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<members[s].size();i++) {
                      ^
icc.cpp: In function 'std::pair<int, int> solve(std::queue<int>, std::queue<int>)':
icc.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[u].size();i++) {
                      ^
icc.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[u].size();i++) {
                      ^
icc.cpp:88:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(s1.size()>siz) {
                        ^
icc.cpp: In function 'std::pair<int, int> solve2(std::queue<int>, std::queue<int>)':
icc.cpp:157:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(s1.size()>siz) {
                    ^
icc.cpp: In function 'void run(int)':
icc.cpp:205:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[reps.first].size();i++) {
                      ^
icc.cpp:208:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[reps.second].size();i++) {
                      ^

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