oj.uz

Submission #1056679

# Submission time Handle Problem Language Result Execution time Memory
1056679 2024-08-13T10:35:56 Z ljtunas 스파이 (JOI13_spy) C++17
30 / 100
 270 ms 262144 KB 
#include <bits/stdc++.h>// "i will win voi25"
using namespace std;

#define fi first
#define se second
#define Forv(v, h)    for(auto &v : h)
#define For(i, a, b)  for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define all(h)        h.begin(), h.end()
#define reset(h, v)   (memset(h, v, sizeof(h)))
#define c_bit(i)       __builtin_popcountll(i)
#define Bit(mask, i)    ((mask >> i) & 1)
#define onbit(mask, i)  ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))

using ll  = long long;
using ii  = pair<ll, ll>;
using vi  = vector<ll>;
using vvi = vector<vi>;
using vii = vector<ii>;

template <class X, class Y> bool maximize(X &a, const Y &b)
{
    if(a < b) return a = b, true;
    return false;
}

template <class X, class Y> bool minimize(X &a, const Y &b)
{
    if(a > b) return a = b, true;
    return false;
}

// #define int long long

const int dx[] = {0, -1, +1, 0}, dy[] = {-1, 0, 0, +1};
const ll oo = 1e18 + 1, base = 311, block = 500;
const ll MOD = 1e9 + 7;
const int MAXN = 5e5  + 5;

int n, m, rA, rB;
vector <int> gA[MAXN];
vector <int> gB[MAXN];

int r[MAXN], s[MAXN], inA[MAXN], inB[MAXN], enA[MAXN], enB[MAXN], idA[MAXN], idB[MAXN];

void dfsa (int u, int par) {
    static int timedfs = 0;
    inA[u] = ++timedfs, idA[timedfs] = u;
    for (int v : gA[u]) dfsa(v, u);
    enA[u] = timedfs;
}

void dfsb (int u, int par) {
    static int timedfs = 0;
    inB[u] = ++timedfs, idB[timedfs] = u;
    for (int v : gB[u]) dfsb(v, u);
    enB[u] = timedfs;
}

vector <int> vecA[MAXN], vecB[MAXN];
vector <int> mp[MAXN];

void process()
{
    cin >> n >> m;
    For (i, 1, n) {
        int pa, pb;
        cin >> pa >> pb;
        if (!pa) rA = i;
        if (!pb) rB = i;
        gA[pa].push_back(i), gB[pb].push_back(i);
    }
    dfsa(rA, 0), dfsb(rB, 0);
    For (i, 1, m) {
        cin >> r[i] >> s[i];
        mp[r[i]].push_back(s[i]);
        For (j, inA[r[i]], enA[r[i]]) vecA[idA[j]].emplace_back(r[i]);
        For (j, inB[s[i]], enB[s[i]]) vecB[idB[j]].emplace_back(s[i]);
    }
    For (i, 1, n) {
        sort (all(vecA[i]));
        vecA[i].resize(distance(vecA[i].begin(), unique(all(vecA[i]))));
        sort (all(vecB[i]));
        vecB[i].resize(distance(vecB[i].begin(), unique(all(vecB[i]))));
    }
    vector <int> cnt(n + 10, 0);
    For (i, 1, n) {
        int ans = 0;
        Forv(y, vecA[i]) {
            for (auto &v : mp[y]) cnt[v] ++;
        }
        Forv(x, vecB[i]) ans += cnt[x];
        Forv(y, vecA[i]) {
            for (auto &v : mp[y]) cnt[v] --;
        }
        cout << ans << '\n';
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #define name "a"
    if (fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    //int tc = 1; cin >> tc; while (tc--)
    process(); // -> ac
    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return 0;
}

Compilation message

spy.cpp: In function 'int32_t main()':
spy.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
spy.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 75100 KB Output is correct
2 Correct 14 ms 75100 KB Output is correct
3 Correct 14 ms 75008 KB Output is correct
4 Correct 11 ms 75100 KB Output is correct
5 Correct 10 ms 74844 KB Output is correct
6 Correct 10 ms 75100 KB Output is correct
7 Correct 10 ms 74804 KB Output is correct
8 Correct 10 ms 74844 KB Output is correct
9 Correct 11 ms 74588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 97064 KB Output is correct
2 Correct 118 ms 107092 KB Output is correct
3 Correct 55 ms 91216 KB Output is correct
4 Correct 84 ms 107092 KB Output is correct
5 Correct 20 ms 75868 KB Output is correct
6 Correct 100 ms 107336 KB Output is correct
7 Correct 37 ms 79452 KB Output is correct
8 Correct 17 ms 75612 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 270 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -