이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |