oj.uz

답안 #46760

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46760 2018-04-22T22:57:09 Z wzy CEOI16_icc (CEOI16_icc) C++11
18 / 100
 387 ms 916 KB 
    #include <bits/stdc++.h>
    #include "icc.h"
    using namespace std;
    #define pb push_back
    int pai[150] , peso[150];
     
    vector<int> linked[152];
     
    int fd(int x){
    	return pai[x] == x ? x : pai[x] = fd(pai[x]);
    }
     
    void join(int u , int v){
    	u = fd(u) , v= fd(v);
    	if(peso[u] > peso[v]) swap(u,v);
    	pai[u] = v , peso[v] += peso[u] + 1;
    	for(int j = 0 ; j < linked[u].size() ; j++) linked[v].push_back(linked[u][j]);
    	linked[u].clear();
    }
     
    bool queryL(int a , int b , vector<int> x , vector<int> y){
    	int xx[150] , yy[150];
    	for(int i = 0 ; i < a ; i++) xx[i] = x[i];
    	for(int i = 0 ; i < b ; i++) yy[i] = y[i];
    	return query(a , b , xx , yy);
    }
     
    bool get(vector<int> l , vector<int> r){
    	if(l.size() == 0 || r.size() == 0) return 0;
    	bool w = queryL(l.size() , r.size() , l , r);
    	if(!w){
    		vector<int> ll , rr;
    		for(int i = 0 ; i < l.size() ; i++){
    			if(ll.size() && fd(ll.back()) == fd(l[i])){
    				ll.pb(l[i]);
    			}
    			else if(rr.size() && fd(rr.back()) == fd(l[i])) rr.pb(l[i]);
    			else{
    				if(ll.size() < rr.size()) ll.pb(l[i]);
    				else rr.pb(l[i]);
    			}
    		}
    		bool q = get(ll , rr);
    		if(!q){
    			vector<int> lr, rl;
    			for(int i = 0 ; i < r.size() ; i++){
    				if(lr.size() && fd(r[i]) == fd(lr.back())){
    					lr.pb(r[i]);
    				}	
    				else if(rl.size() && fd(r[i]) == fd(rl.back())) rl.pb(r[i]);
    				else{
    					if(lr.size() < rl.size()) lr.pb(r[i]);
    					else rl.pb(r[i]);
    				}
    			}
    			q = get(lr , rl);
    		}
    		return q;
    	}
    	else{
    		int ll = 0 , rr = l.size() - 1;
    		int ansj = -1;
    		while(ll<=rr){
    			int mid = (ll + rr) / 2;
    			vector<int> opt;
    			for(int j = 0 ; j <= mid ; j++) opt.pb(l[j]);
    			bool q = queryL(opt.size() , r.size() , opt, r);
    			if(q){
    				rr = mid - 1;
    				ansj = mid;
    			}
    			else ll = mid + 1;
    		}
    		ll = 0 , rr = r.size() - 1;
    		int ansj2 = -1;
    		while(ll <= rr){
    			int mid = (ll +rr)/2;
    			vector<int> opt;
    			for(int j = 0 ; j <= mid; j++) opt.pb(r[j]);
    				bool q = queryL(opt.size() , l.size() , opt, l);
    			if(q){
    				rr = mid - 1;
    				ansj2 = mid;
    			}
    			else ll = mid + 1;
    		}
          	join(l[ansj] , r[ansj2]);
    		setRoad(l[ansj] , r[ansj2]);
    		return true;
    	}
    }
     
     
    void run(int n){
    	for(int i = 0 ; i <= n; i++) pai[i] = i , peso[i] = 0 , linked[i].pb(i);
    	for(int i = 0 ; i < n - 1 ; i++){
    		set<int> dependencies;
    		for(int j = 1 ; j <= n; j ++) dependencies.insert(j);
    		vector<int> l , r;
    		for(int j = 1 ; j <= n; j++){
    			if(!dependencies.count(j)) continue;
    			if(l.size() < r.size()){
    				for(int w = 0 ; w < linked[fd(j)].size() ; w++){
    					l.pb(linked[fd(j)][w]);
    					dependencies.erase(linked[fd(j)][w]);
    				}
    			}
    			else{
    				for(int w = 0 ; w < linked[fd(j)].size(); w++){
    					r.pb(linked[fd(j)][w]);
    					dependencies.erase(linked[fd(j)][w]);
    				}
    			}
    		}
    		get(l , r);
    	}
    }

Compilation message

icc.cpp: In function 'void join(int, int)':
icc.cpp:17:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0 ; j < linked[u].size() ; j++) linked[v].push_back(linked[u][j]);
                      ~~^~~~~~~~~~~~~~~~~~
icc.cpp: In function 'bool get(std::vector<int>, std::vector<int>)':
icc.cpp:33:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0 ; i < l.size() ; i++){
                       ~~^~~~~~~~~~
icc.cpp:46:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int i = 0 ; i < r.size() ; i++){
                        ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:103:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int w = 0 ; w < linked[fd(j)].size() ; w++){
                         ~~^~~~~~~~~~~~~~~~~~~~~~
icc.cpp:109:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int w = 0 ; w < linked[fd(j)].size(); w++){
                         ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 504 KB Ok! 104 queries used.
2 Correct 10 ms 616 KB Ok! 117 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 684 KB Ok! 953 queries used.
2 Correct 101 ms 744 KB Ok! 1390 queries used.
3 Correct 108 ms 856 KB Ok! 1414 queries used.

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 374 ms 856 KB Too many queries! 3908 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 387 ms 860 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 332 ms 916 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 306 ms 916 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -