제출 #312738

#제출 시각아이디문제언어결과실행 시간메모리
312738mohamedsobhi777ICC (CEOI16_icc)C++14
90 / 100
217 ms1048 KiB
#include<bits/stdc++.h> #include "icc.h" #define I inline void #define S struct #define vi vector<int> #define vii vector<pair<int,int>> #define pii pair<int,int> #define pll pair<ll,ll> using namespace std ; using ll = long long ; using ld = long double ; const int N = 1e5 + 7 , mod = 1e9 + 7 ; const int inf = N ; // How interesting! int n ; int fat[N] ; vector<pair<int,int> > ed ; int U , V ; inline int find(int x){return fat[x] = (x == fat[x] ? x : find(fat[x])) ; } void link(int u , int v){ u = find(u) ; v = find(v) ; if(u!=v) fat[u] = v; } /* bool ok(int u , int v){ if( u == U && v == V) return 1 ; if(u == V && v == U) return 1; return 0 ; } void setRoad(int u , int v){ if(ok(u , v)){ cout<<"ok " << u <<" " << v <<"\n" ; link(u , v) ; } else{ cout<< u <<" "<< v <<">>" ; cout<<"bad" ; exit(0) ; } } int query(int x , int y , vector<int> v1 , vector<int> v2){ set<int> st ; for(auto u : v1) st.insert(find(u)) ; for(auto u : v2){ if(st.find(find(u)) != st.end()) return 1 ; } int m1 = 0 , m2 = 0 ; for(auto u : v1) if(u == U || u == V) m1 = 1; for(auto u : v2) if(u == U || u == V) m2 = 1 ; if( m1 == 1 && m2 == 1 ){ return 1 ; } return 0 ; }*/ int query1(int x , int y , vector<int> v1 , vector<int> v2){ //return query(x , y , v1 , v2) ; int *v11; int *v22 ; v11 = new int[x] ; v22 = new int [y] ; for(int i = 0 ;i < x ; ++ i) v11[i] = v1[i] ; for(int i = 0 ;i < y ; ++ i) v22[i] = v2[i] ; return query(x , y , v11 , v22) ; } void divide(vector<vector<int> > &vec){ vector<vector<int> > ret ; int sz = (int) vec.size() ; for(int i = 0 ;i < sz ; ++ i){ int sz2 = (int) vec[i].size() ; vector<int> lhs, rhs ; for(int j = 0 ;j < sz2 ;++ j){ if(j < sz2 / 2 ) lhs.push_back(vec[i][j]) ; else rhs.push_back(vec[i][j]) ; } if(lhs.size()) ret.push_back(lhs) ; if(rhs.size()) ret.push_back(rhs) ; } vec = ret ; } vector<int> chd(int x){ vector<int> ret ; for(int i = 1 ;i <= n; ++ i){ if(find(i) == x) ret.push_back(i) ; } return ret ; } int conquer(vector<vector<int> > &vec, int lmt = 1000000){ int ret = 0 ; vector<int> lhs, rhs ; for(int i = 0 ; i < min(lmt , (int) vec.size() ) ; ++ i){ for(auto u : vec[i]){ if(i&1) for(auto v : chd(u)) rhs.push_back(v) ; else for(auto v : chd(u)) lhs.push_back(v) ; } } return query1(lhs.size() , rhs.size() , lhs , rhs ) ; } vector<int> qur(vector<int> ve){ vector<int> ret ; for(auto u : ve) for(auto v : chd(u)) ret.push_back(v) ; return ret; } void getRoad(vector<int> v1, vector<int> v2){ vector<int> now = v1, oth = v2 ; int lo = 1 , hi = v1.size() ; int u = 0 , v = 0 ; while(lo<=hi){ int mid = (lo+hi)>>1; vector<int> nnow ; for(int i = 0 ; i < mid ; ++ i) nnow.push_back(now[i]) ; if(query1(nnow.size() ,oth.size(),nnow,oth)){ hi = mid - 1; u = nnow.back() ; }else{ lo = mid + 1; } } swap(now,oth) ; swap(u , v) ; lo = 1, hi = (int) now.size() ; while(lo<=hi){ int mid = (lo+hi)>>1; vector<int> nnow ; for(int i = 0 ; i < mid ; ++ i) nnow.push_back(now[i]) ; if(query1(nnow.size() ,oth.size(),nnow,oth)){ hi = mid - 1; u = nnow.back() ; }else{ lo = mid + 1; } } setRoad(u , v) ; link(u , v) ; } void divide_or_conquer(vector<int> hs){ vector<vector<int> > dac { hs } ; divide(dac) ; while(!conquer(dac))divide(dac) ; int lo = 1, hi = (int) dac.size() ; int lst = (int) dac.size() ; while(lo<=hi){ int mid = (lo+hi) >> 1; if(conquer(dac, mid)){ lst = mid ; hi = mid - 1; }else lo = mid + 1; } getRoad(qur(dac[lst-2]) , qur(dac[lst-1]) ) ; } void run(int x){ n = x; for(int i = 1;i <= n; ++ i) fat[i] = i ; for(int r = 0 ; r < n - 1; ++ r){ //U = ed[r].first ; //V = ed[r].second ; vector<int> v ; for(int i = 1;i <= n; ++ i){ if(i == fat[i]) v.push_back(i) ; } random_shuffle(v.begin() , v.end()) ; divide_or_conquer(v) ; } }

컴파일 시 표준 에러 (stderr) 메시지

icc.cpp: In function 'int conquer(std::vector<std::vector<int> >&, int)':
icc.cpp:119:13: warning: unused variable 'ret' [-Wunused-variable]
  119 |         int ret = 0 ;
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...