Submission #1069317

#TimeUsernameProblemLanguageResultExecution timeMemory
1069317hasan2006Connecting Supertrees (IOI20_supertrees)C++17
40 / 100
153 ms22184 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define se second #define fi first #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 2e5 + 9 , mod = 1e9 + 7; ll a[N] , b[N] , dp[N]; //int press(string a){} int construct(vector<vector<int>> v){ ll i , j , l , r , s = 0, f , n , m , x , y , k; n = v.size(); vector<vector<int>>c(n); for(i = 0; i < n; i++) c[i].resize(n); for(i = 0; i < n; i++){ if(b[i] != 0) continue; vector<pair<int,pair<int,int>>>vc; vector<int>v1 , v2 , v3; for(j = 0; j < n; j++) if(v[i][j] != 0) b[j] = 1 , v1.pb(j); l = r = 0; for(x = 0; x < v1.size(); x++) for(y = x + 1; y < v1.size(); y++){ vc.pb({v[v1[x]][v1[y]] , {v1[x] , v1[y]}}); if(v[v1[x]][v1[y]] == 2) l = 1; if(v[v1[x]][v1[y]] == 3) r = 1; } sort(all(vc)); if(v1.size() == 1) continue; if((l == 1 && r == 1) || vc.front().fi == 0){ return 0; } for(auto to : vc) if(to.fi == 1 && to.se.fi != to.se.se) b[to.se.fi] = b[to.se.se] = 2; set<int>st; for(auto to : v1){ st.insert(to); if(b[to] == 1) v2.pb(to); else v3.pb(to); } f = -1; for(auto to : v3){ if(f != -1) c[to][f] = c[f][to] = 1; f = to; } if(v2.size()){ if(v3.size()) v2.pb(v3.back()); if(v2.size() <= vc.back().fi){ return 0; } f = v2.back(); for(auto to : v2) c[f][to] = c[to][f] = 1 , f = to; if(vc.back().fi == 3) c[v2[0]][v2[2]] = c[v2[2]][v2[0]] = 1; } for(auto to : v1){ ll L = 0 ,R = 0 , s =0; for(j = 0; j < n ; j++) if(v[to][j] != 0){ if(st.find(j) == st.end()) return 0; s++; if(to == j) continue; if(v[to][j] == 2) L = 1; else if(v[to][j] == 3) R = 1; else { if(b[to] == 1 || b[j] == 1) return 0; } } // if((L > l) || (R > r) || s != v1.size()) // return 0; } } /* for(i = 0; i < n; i++){ for(j = 0; j < n; j++) cout<<c[i][j]<<" "; cout<<"\n"; }*/ build(c); return 1; } /* int main(){ #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif }*/ // Author : حسن

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:42:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(x = 0; x < v1.size(); x++)
      |                    ~~^~~~~~~~~~~
supertrees.cpp:43:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(y = x + 1; y < v1.size(); y++){
      |                            ~~^~~~~~~~~~~
supertrees.cpp:77:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |             if(v2.size() <= vc.back().fi){
      |                          ^
supertrees.cpp:87:16: warning: variable 'L' set but not used [-Wunused-but-set-variable]
   87 |             ll L = 0 ,R = 0 , s =0;
      |                ^
supertrees.cpp:87:23: warning: variable 'R' set but not used [-Wunused-but-set-variable]
   87 |             ll L = 0 ,R = 0 , s =0;
      |                       ^
supertrees.cpp:27:24: warning: unused variable 's' [-Wunused-variable]
   27 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                        ^
supertrees.cpp:27:40: warning: unused variable 'm' [-Wunused-variable]
   27 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                        ^
supertrees.cpp:27:52: warning: unused variable 'k' [-Wunused-variable]
   27 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                                    ^
#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...