제출 #399879

#제출 시각아이디문제언어결과실행 시간메모리
399879AugustinasJucas열대 식물원 (Tropical Garden) (IOI11_garden)C++14
100 / 100
4681 ms58516 KiB
#pragma GCC optimize("O3") #include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> using namespace std; const int dydis = 2 * 150000 + 10; vector<pair<int, int> > gr[dydis]; int n, m; int nxt[dydis]; vector<int> rev[dydis]; bool vis[dydis] = {}; bool on[dydis] = {}; bool inCyc[dydis] = {}; int revCyc[dydis]; vector<int> cur; vector<int> cyc; vector<pair<int, int> > dst[dydis]; vector<int> visi; int sz[dydis] = {0}; bool used[dydis]; void dfs(int v){ //cout << "v = " << v << endl; if(cyc.size() != 0) return; if(vis[v]){ if(!on[v]) return ; while(true){ cyc.push_back(cur.back()); int lst = cur.back(); cur.pop_back(); if(lst == v) break; } return ; } vis[v] = 1; on[v] = 1; cur.push_back(v); dfs(nxt[v]); on[v] = 0; if(cur.size())cur.pop_back(); } void dfs1(int v, int came, int real, int h = 0){ // if(v != real){ dst[real].push_back({v, h}); // cout << "dst " << real << ", pb " << v << ", dst = " << h << endl; // } for(auto x : rev[v]){ if(x == came || inCyc[x]) continue; dfs1(x, v, real, h+1); } } void dfs2(int v, int came, int left){ int ret = 0; if(left == 0) { if(!(v & 1)) visi.push_back(v/2); return; } for(auto x : rev[v]){ if(x == came) continue; dfs2(x, v, left-1); } } void darom(int v, int k){ int P = v; //cout << "kiek nuo " << v << " " << k << endl; if(!inCyc[v]){ if(k > n) return ; dfs2(v, -1, k); }else{ // cout << "darau nuo " << v << endl; int dist = 0; while(true){ // cout << "v = " << v << ", nuo jo iki " << P << " dst = " << dist << endl; for(auto x : dst[v]){ if(x.first & 1) continue; if(x.second + dist > k) continue; //cout << "bandau " << x.first/2 << endl; if((k-x.second) % sz[P] == dist){ visi.push_back(x.first/2); } // jo atstumas yra } dist++; v = revCyc[v]; if(v == P) break; } } } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { //cout << "start" << endl; n = N; m = M; for(int i = 0; i < m; i++){ gr[R[i][0]].push_back({R[i][1], i}); gr[R[i][1]].push_back({R[i][0], i}); } //for(int i = 0; i < n; i++) reverse(gr[i].begin(), gr[i].end()); for(int i = 0; i < 2 * n; i++){ int v = i / 2; int kt = -1; int kn = 0; if(i & 1) { // atejau is didziausio savo if(gr[v].size() == 1){ kt = gr[v][0].first; kn = gr[v][0].second; }else{ kt = gr[v][1].first; kn = gr[v][1].second; } }else{ kt = gr[v][0].first; kn = gr[v][0].second; } if(gr[kt][0].second == kn){ nxt[i] = 2 * kt + 1; rev[2*kt+1].push_back(i); }else{ nxt[i] = 2 * kt; rev[2*kt].push_back(i); } // cout << "nxt[" << i << "] = " << nxt[i] << endl; } for(int i = 0; i < 2*n; i++){ if(vis[i]) continue; cur.clear(); cyc.clear(); dfs(i); if(cyc.size() == 0) continue; // cout << "cyc = "; for(auto x : cyc) cout << x << " "; cout << "\n"; for(auto x : cyc) inCyc[x] = 1; for(auto x : cyc) dfs1(x, x, x); for(int i = 0; i < cyc.size(); i++){ revCyc[cyc[(i-1 + cyc.size())%cyc.size()]] = cyc[i]; sz[cyc[i]] = cyc.size(); } } for(int i = 0; i < Q; i++){ int k = G[i]; darom(P*2, k); darom(P*2+1, k); int cnt = 0; for(auto x : visi){ if(!used[x]) cnt++; used[x] = 1; } //cout << "visi: "; for(auto x : visi) cout << x << " "; for(auto x : visi) used[x] = 0; visi.clear(); answer(cnt); } // visada pradesiu nuo 2 * v; }

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

garden.cpp: In function 'void dfs2(int, int, int)':
garden.cpp:53:9: warning: unused variable 'ret' [-Wunused-variable]
   53 |     int ret = 0;
      |         ^~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:132:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for(int i = 0; i < cyc.size(); i++){
      |                        ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...