Submission #100653

#TimeUsernameProblemLanguageResultExecution timeMemory
100653Pro_ktmrSnowy Roads (JOI16_snowy)C++14
20 / 100
20 ms1856 KiB
#include"bits/stdc++.h" using namespace std; #include"Anyalib.h" #define MP(a,b) make_pair(a,b) static int n; static int par[500]; static int toPar[500]; static int d[500] = {}; static int depth(int i){ if(i == 0) return 0; if(d[i] != 0) return d[i]; return d[i] = 1 + depth(par[i]); } static vector<int> ls; void InitAnya(int N, int A[], int B[]){ n = N; vector<pair<int,int> > tonari[500]; for(int i=0; i<N-1; i++){ tonari[A[i]].push_back(MP(B[i],i)); tonari[B[i]].push_back(MP(A[i],i)); } par[0] = 0; toPar[0] = -1; queue<int> que; que.push(0); while(!que.empty()){ int now = que.front(); que.pop(); for(int i=0; i<tonari[now].size(); i++){ if(tonari[now][i].first == par[now]) continue; par[tonari[now][i].first] = now; toPar[tonari[now][i].first] = tonari[now][i].second; que.push(tonari[now][i].first); } } for(int i=0; i<n; i++){ if(depth(i)%9 == 0) ls.push_back(i); } ls.push_back(n); } //void Save(int place, int bit) static int C2[500]; static int memo[500]; static int wa(int i){ if(memo[i] != -1) return memo[i]; return memo[i] = wa(par[i]) + C2[toPar[i]]; } void Anya(int C[]){ for(int i=1; i<n; i++) Save(i, C[toPar[i]]); for(int i=0; i<n-1; i++) C2[i] = C[i]; for(int i=0; i<n; i++) memo[i] = -1; memo[0] = 0; for(int i=0; i<n; i++){ int tmp = wa(i); if(*lower_bound(ls.begin(), ls.end(), i) == i){ int idx = lower_bound(ls.begin(), ls.end(), i) - ls.begin(); for(int j=0; j<10; j++){ Save(500+idx*10+j, (tmp>>(9-j))%2); } } } }
#include"bits/stdc++.h" using namespace std; #include"Borislib.h" #define MP(a,b) make_pair(a,b) static int n; static int par[500]; static int toPar[500]; static int d[500] = {}; static int depth(int i){ if(i == 0) return 0; if(d[i] != 0) return d[i]; return d[i] = 1 + depth(par[i]); } static vector<int> ls; void InitBoris(int N, int A[], int B[]){ n = N; vector<pair<int,int> > tonari[500]; for(int i=0; i<N-1; i++){ tonari[A[i]].push_back(MP(B[i],i)); tonari[B[i]].push_back(MP(A[i],i)); } par[0] = 0; queue<int> que; que.push(0); while(!que.empty()){ int now = que.front(); que.pop(); for(int i=0; i<tonari[now].size(); i++){ if(tonari[now][i].first == par[now]) continue; par[tonari[now][i].first] = now; toPar[tonari[now][i].first] = tonari[now][i].second; que.push(tonari[now][i].first); } } for(int i=0; i<n; i++){ if(depth(i)%9 == 0) ls.push_back(i); } } //Ask(int place) int Boris(int city){ int ans = 0; int now = city; while(*lower_bound(ls.begin(), ls.end(), now) != now){ ans += Ask(now); now = par[now]; } int idx = lower_bound(ls.begin(), ls.end(), now) - ls.begin(); for(int i=0; i<10; i++){ ans += Ask(500+idx*10+i)<<(9-i); } return ans; }

Compilation message (stderr)

Anya.cpp: In function 'void InitAnya(int, int*, int*)':
Anya.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<tonari[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~~~

Boris.cpp: In function 'void InitBoris(int, int*, int*)':
Boris.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<tonari[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...