Submission #30696

#	Time	Username	Problem	Language	Result	Execution time	Memory
30696		jenkhai	ICC (CEOI16_icc)	C++14	18 / 100	373 ms	2372 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;

bool check(queue<int> q1, queue<int> q2) {
    int size_a=0, size_b=0, a[MAXN], b[MAXN];
    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");
    }
    //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");
    }
    return query(size_a, size_b, a, b);
}

pair<int, int> solve3(queue<int> q1, queue<int> q2) {
    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];
    
    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(s1.size() > s2.size()) {
        while(!s2.empty()) {
            q2.push(s2.top()); s2.pop();
        }
        int siz = s1.size()/2;

        while(s1.size()>siz) {
            q1.push(s1.top()); s1.pop();
        }
        if(check(q1, q2)) return solve3(q1,q2);

        q1 = queue<int>();

        while(!s1.empty()) {
            q1.push(s1.top()); s1.pop();
        }
        if(check(q1, q2)) return solve3(q1,q2);
    } else {
        while(!s1.empty()) {
            q1.push(s1.top()); s1.pop();
        }
        int siz = s2.size()/2;
        while(s2.size()>siz) {
            q2.push(s2.top()); s2.pop();
        }
        if(check(q1, q2)) return solve3(q1,q2);
        q2 = queue<int>();
        while(!s2.empty()) {
            q2.push(s2.top()); s2.pop();
        }
        if(check(q1, q2)) return solve3(q1,q2);
    }

    return make_pair(-1, -1);
}

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)) { //across
        while(!s1.empty()) {
            q1.push(s1.top()); s1.pop();
        }
        while(!s2.empty()) {
            q2.push(s2.top()); s2.pop();
        }
        return solve3(q1, q2);
    } 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) {
    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());
    //printf("qq1: ");
    while(!q1.empty()) {
        int u = q1.front(); q1.pop();   
        a[size_a++] = u;
        //printf("%d ", u);
        s1.push(u);
    }
    //printf("qq2: ");
    while(!q2.empty()) {
        int u = q2.front(); q2.pop();
        b[size_b++] = u;
        //printf("%d ", u);
        s2.push(u);
    }
    //printf("\n");

    //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;
    if(s1.size() > s2.size()) {
        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;

        q1 = queue<int>();

        while(!s1.empty()) {
            q1.push(s1.top()); s1.pop();
        }
        ret = solve2(q1, q2);
        if(ret.first != -1) return ret;
    } else {
        while(!s1.empty()) {
            q1.push(s1.top()); s1.pop();
        }
        int siz = s2.size()/2;
        while(s2.size()>siz) {
            q2.push(s2.top()); s2.pop();
        }
        ret = solve2(q1, q2);
        if(ret.first != -1) return ret;
        q2 = queue<int>();
        while(!s2.empty()) {
            q2.push(s2.top()); s2.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);
}
int done[150][150];
void print(int N) {
    //printf("TRUE EDGES:\n");
    for(int i=1;i<=N;i++) {
        for(int j=i+1;j<=N;j++) {
            if(done[i][j] || done[j][i]) continue;
            if(test(i, j)) {
                done[i][j] = 1;
                done[j][i] = 1;
                //printf("%d %d\n", i, j);    
                setRoad(i, j);
                return;
            }
        }
    }
    //printf("===THE END===\n");
}

void print2(int N) {
    //printf("TRUE EDGES:\n");
    for(int i=1;i<=N;i++) {
        for(int j=i+1;j<=N;j++) {
            if(done[i][j] || done[j][i]) continue;
            if(test(i, j)) {
                printf("TRUE:%d %d\n", i, j);    
                return;
            }
        }
    }
    //printf("===THE END===\n");
}

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

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 'bool check(std::queue<int>, std::queue<int>)':
icc.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[u].size();i++) {
                      ^
icc.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[u].size();i++) {
                      ^
icc.cpp: In function 'std::pair<int, int> solve3(std::queue<int>, std::queue<int>)':
icc.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[u].size();i++) {
                      ^
icc.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[u].size();i++) {
                      ^
icc.cpp:97:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(s1.size()>siz) {
                        ^
icc.cpp:113:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(s2.size()>siz) {
                        ^
icc.cpp: In function 'std::pair<int, int> solve(std::queue<int>, std::queue<int>)':
icc.cpp:148:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[u].size();i++) {
                      ^
icc.cpp:157:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[u].size();i++) {
                      ^
icc.cpp: In function 'std::pair<int, int> solve2(std::queue<int>, std::queue<int>)':
icc.cpp:231:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(s1.size()>siz) {
                        ^
icc.cpp:249:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(s2.size()>siz) {
                        ^
icc.cpp: In function 'void run(int)':
icc.cpp:320:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[reps.first].size();i++) {
                      ^
icc.cpp:325:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<UF.members[reps.second].size();i++) {
                      ^

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