이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
if (sz(s))
{
freopen((s + ".in").c_str(), "r", stdin);
if (s != "test1")
freopen((s + ".out").c_str(), "w", stdout);
}
}
#ifndef arwaeystoamneg
#include "garden.h"
#include "gardenlib.h"
#endif
#ifdef arwaeystoamneg
#define MAX_M 1000000
#define MAX_Q 2000
static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;
inline
void my_assert(int e) { if (!e) abort(); }
void read_input()
{
int i;
my_assert(3 == scanf("%d %d %d", &N, &M, &P));
for (i = 0; i < M; i++)
my_assert(2 == scanf("%d %d", &R[i][0], &R[i][1]));
my_assert(1 == scanf("%d", &Q));
for (i = 0; i < Q; i++)
my_assert(1 == scanf("%d", &G[i]));
for (i = 0; i < Q; i++)
my_assert(1 == scanf("%d", &solutions[i]));
}
void answer(int x)
{
if (answer_count >= Q) {
printf("Incorrect. Too many answers.\n");
exit(0);
}
answers[answer_count] = x;
answer_count++;
}
#endif
const int MAX = 150005;
int n, p, a[2 * MAX], indeg[2 * MAX], cyc[2 * MAX], k = 1, type[2 * MAX], sizes[2 * MAX];
pii win[MAX][2];
vi adj[MAX], back[2 * MAX];
void dfs(int i)
{
if (type[i])return;
assert(cyc[i]);
sizes[k]++;
type[i] = k;
dfs(a[i]);
}
int check(pii t, int k)
{
return k >= t.s && (k - t.s) % t.f == 0;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
p = P;
F0R(i, M)
{
adj[R[i][0]].pb(R[i][1]);
adj[R[i][1]].pb(R[i][0]);
}
F0R(i, n)
{
a[2 * i] = 2 * adj[i][0] + (i == adj[adj[i][0]][0]);
a[2 * i + 1] = 2 * adj[i][min(sz(adj[i]) - 1, 1)] + (i == adj[adj[i][min(sz(adj[i]) - 1, 1)]][0]);
}
// F0R(i, 2 * n)cout << i << " " << a[i] << endl;
F0R(i, 2 * n)indeg[a[i]]++;
vi todo;
F0R(i, 2 * n)if (!indeg[i])todo.push_back(i);
F0R(i, sz(todo))
{
indeg[a[todo[i]]]--;
if (!indeg[a[todo[i]]])todo.push_back(a[todo[i]]);
}
F0R(i, 2 * n)if (indeg[i])cyc[i] = 1;
// cout << endl << endl; F0R(i, 2 * n)cout << i << " " << cyc[i] << endl;
F0R(i, 2 * n)
{
if (cyc[i] && type[i] == 0)
{
dfs(i);
k++;
}
}
// cout << endl << endl; F0R(i, 2 * n)cout << i << " " << type[i] << endl;
// cout << endl << endl; F0R(i, k)cout << i << " " << sizes[i] << endl;
F0R(i, 2 * n)back[a[i]].pb(i);
F0R(i, n)win[i][0] = win[i][1] = { inf,inf };
int dist[2 * MAX];
if (cyc[2 * p])
{
F0R(i, 2 * n)dist[i] = inf;
dist[2 * p] = 0;
vi todo = { 2 * p };
F0R(i, sz(todo))
{
trav(x, back[todo[i]])
{
if (dist[x] > dist[todo[i]] + 1)
{
dist[x] = dist[todo[i]] + 1;
todo.pb(x);
}
}
}
for (int i = 0; i < 2 * n; i += 2)
{
if (dist[i] != inf)
{
win[i / 2][0] = { sizes[type[2 * p]],dist[i] };
}
}
}
else
{
F0R(i, 2 * n)dist[i] = inf;
dist[2 * p] = 0;
vi todo = { 2 * p };
F0R(i, sz(todo))
{
trav(x, back[todo[i]])
{
dist[x] = dist[todo[i]] + 1;
todo.pb(x);
}
}
for (int i = 0; i < 2 * n; i += 2)
{
if (dist[i] != inf)
{
win[i / 2][1] = { inf,dist[i] };
}
}
}
if (cyc[2 * p + 1])
{
F0R(i, 2 * n)dist[i] = inf;
dist[2 * p + 1] = 0;
vi todo = { 2 * p + 1 };
F0R(i, sz(todo))
{
trav(x, back[todo[i]])
{
if (dist[x] > dist[todo[i]] + 1)
{
dist[x] = dist[todo[i]] + 1;
todo.pb(x);
}
}
}
for (int i = 0; i < 2 * n; i += 2)
{
if (dist[i] != inf)
{
win[i / 2][0] = { sizes[type[2 * p + 1]],dist[i] };
}
}
}
else
{
F0R(i, 2 * n)dist[i] = inf;
dist[2 * p + 1] = 0;
vi todo = { 2 * p + 1 };
F0R(i, sz(todo))
{
trav(x, back[todo[i]])
{
dist[x] = dist[todo[i]] + 1;
todo.pb(x);
}
}
for (int i = 0; i < 2 * n; i += 2)
{
if (dist[i] != inf)
{
win[i / 2][1] = { inf,dist[i] };
}
}
}
F0R(i, Q)
{
int k = G[i];
int ans = 0;
F0R(j, n)
{
if (check(win[j][0], k))
{
ans++;
assert(!check(win[j][1], k));
}
else
{
if (check(win[j][1], k))
ans++;
}
}
answer(ans);
}
}
#ifdef arwaeystoamneg
int main()
{
setIO("test1");
int correct, i;
read_input();
answer_count = 0;
count_routes(N, M, P, R, Q, G);
if (answer_count != Q) {
printf("Incorrect. Too few answers.\n");
exit(0);
}
correct = 1;
for (i = 0; i < Q; i++)
if (answers[i] != solutions[i])
correct = 0;
if (correct)
printf("Correct.\n");
else {
printf("Incorrect.\n");
printf("Expected: ");
for (i = 0; i < Q; i++)
printf("%d ", solutions[i]);
printf("\nReturned: ");
for (i = 0; i < Q; i++)
printf("%d ", answers[i]);
}
return 0;
}
#endif
컴파일 시 표준 에러 (stderr) 메시지
garden.cpp: In function 'void setIO(std::string)':
garden.cpp:48:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
48 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:50:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
50 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |