oj.uz

Submission #101859

# Submission time Handle Problem Language Result Execution time Memory
101859 2019-03-20T14:43:40 Z ShaneOng ICC (CEOI16_icc) C++14
90 / 100
 187 ms 640 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int n;
typedef pair<int,int> ii;
vector<int> p,rnk,adj[109];
int findS(int a){
    return a==p[a]?a:(p[a]=findS(p[a]));
}
void unionS(int a,int b){
    if(findS(a)!=findS(b)){
        int i=findS(a),j=findS(b);
        if(rnk[i]<rnk[j])
            p[i]=j;
        else{
            p[j]=i;
            if(rnk[i]==rnk[j])
                rnk[i]++;
        }
    }
}
vector<int> conv(vector<int> a){
    vector<int> newa;
    unordered_set<int> us;
    for(int x:a){
        us.insert(x);
    }
    for(int x=0;x<n;x++)
        if(us.find(findS(x))!=us.end())
            newa.push_back(x+1);
    return newa;
}
ii stuff(vector<int> a,vector<int> b){
    int qu=0;
    if((int)a.size()>0&&(int)b.size()>0){
        vector<int> tempa=conv(a),tempb=conv(b);
        qu=query(tempa.size(),tempb.size(),&tempa[0],&tempb[0]);
    }
    /*printf("\na:");
    for(int x:a)
        printf("%d ",x);
    printf("\n");
    printf("b:");
    for(int x:b)
        printf("%d ",x);
    printf("\n");*/
    int na=(int)a.size(),nb=(int)b.size();
    ii res=ii(-1,-1);
    if(qu==0){
        vector<int> aa,ab,ba,bb;
        if(na>1){
            for(int x=0;x<na;x++){
                if(x<na/2)
                    aa.push_back(a[x]);
                else
                    ab.push_back(a[x]);
            }
            res=max(res,stuff(aa,ab));
        }
        if(nb>1){
            for(int x=0;x<nb;x++){
                if(x<nb/2)
                    ba.push_back(b[x]);
                else
                    bb.push_back(b[x]);
            }
            res=max(res,stuff(ba,bb));
        }

        return res;
    }else{
        a=conv(a),b=conv(b);
        while((int)a.size()>1){
            vector<int> a1,a2;
            for(int x=0;x<(int)a.size();x++){
                if(x<(int)a.size()/2)
                    a1.push_back(a[x]);
                else
                    a2.push_back(a[x]);
            }

            int qu=query(a1.size(),b.size(),&a1[0],&b[0]);
            if(qu==0){
                a=a2;
            }else
                a=a1;
        }
        while((int)b.size()>1){
            vector<int> b1,b2;
            for(int x=0;x<(int)b.size();x++){
                if(x<(int)b.size()/2)
                    b1.push_back(b[x]);
                else
                    b2.push_back(b[x]);
            }
            int qu=query(a.size(),b1.size(),&a[0],&b1[0]);
            if(qu==0){
                b=b2;
            }else
                b=b1;
        }
        //printf("%d %d\n",a[0],b[0]);
        return ii(a[0],b[0]);

    }
}
void run(int nn) {
    n=nn;
    for(int x=0;x<n;x++){
        p.push_back(x);
        rnk.push_back(0);
    }
    for(int x=0;x<n-1;x++){
        int ctr=0;
        ii ans=ii(-1,-1);
        for(int i=0;(1<<i)<n;i++){
            vector<int> arr[2];
            for(int y=0;y<n;y++){
                if(findS(y)==y){
                    arr[(((1<<i)&y)==0)].push_back(y);

                }
            }
            vector<int> tempa=conv(arr[0]),tempb=conv(arr[1]);
            int qu=query(tempa.size(),tempb.size(),&tempa[0],&tempb[0]);;
            if(qu){
                ans=stuff(arr[0],arr[1]);
                break;
            }
        }
        adj[ans.first-1].push_back(ans.second-1);
        adj[ans.second-1].push_back(ans.first-1);
        unionS(ans.second-1,ans.first-1);
        //printf("%d %d\n",ans.first,ans.second);
        setRoad(ans.first,ans.second);
    }
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:114:13: warning: unused variable 'ctr' [-Wunused-variable]
         int ctr=0;
             ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 640 KB Ok! 121 queries used.
2 Correct 11 ms 512 KB Ok! 114 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 564 KB Ok! 602 queries used.
2 Correct 53 ms 560 KB Ok! 735 queries used.
3 Correct 50 ms 552 KB Ok! 726 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 600 KB Ok! 1457 queries used.
2 Correct 149 ms 632 KB Ok! 1746 queries used.
3 Correct 130 ms 512 KB Ok! 1485 queries used.
4 Correct 144 ms 512 KB Ok! 1615 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 632 KB Ok! 1525 queries used.
2 Correct 141 ms 512 KB Ok! 1589 queries used.
3 Correct 159 ms 512 KB Ok! 1734 queries used.
4 Correct 149 ms 636 KB Ok! 1454 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 512 KB Ok! 1744 queries used.
2 Correct 156 ms 564 KB Ok! 1750 queries used.
3 Correct 162 ms 608 KB Ok! 1751 queries used.
4 Correct 153 ms 512 KB Ok! 1705 queries used.
5 Correct 138 ms 576 KB Ok! 1572 queries used.
6 Correct 156 ms 608 KB Ok! 1687 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 632 KB Too many queries! 1745 out of 1625
2 Halted 0 ms 0 KB -