Submission #374928

#	Time	Username	Problem	Language	Result	Execution time	Memory
374928		Killer2501	스파이 (JOI13_spy)	C++14	100 / 100	190 ms	66944 KiB

spy

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "talltree"
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
#define ull unsigned long long
#define vl vlf
#define vr vrt
using namespace std;
const ll mod = 1e9+7;
const ll N = 2005;
vector<ll> kq[2], adj[N][2];
vector<pll> pre[2];
ll n, m, t, k, b[N][N],  a[N][N], tong, d[N][2], cnt, c[N], top[N][2], nchain[N][2], sz[N][2], par[N][2], chain;
ll ans;
map<ll, ll> mp[N];
priority_queue< pll, vector<pll>, greater<pll> > st[N];
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
string s;
void dfs(ll u, ll p, ll id)
{
    sz[u][id] = 1;
    for(ll v : adj[u][id])
    {
        if(v == p)continue;
        par[v][id] = u;
        dfs(v, u, id);
        sz[u][id] += sz[v][id];
    }
}
void hld(ll u, ll p, ll id)
{
    if(top[chain][id] == 0)top[chain][id] = u;
    nchain[u][id] = chain;
    d[u][id] = ++k;
    //cout << u <<" "<<k << " " <<  id << '\n';
    ll big = -1;
    for(ll v : adj[u][id])
    {
        if(v == p)continue;
        if(big == -1 || sz[big][id] < sz[v][id])big = v;
    }
    if(big != -1)hld(big, u, id);
    for(ll v : adj[u][id])
    {
        if(v == p || v == big)continue;
        ++chain;
        hld(v, u, id);
    }
}
ll f(ll l, ll r, ll u, ll v)
{
    return b[u][v] - b[u][r-1] - b[l-1][v] + b[l-1][r-1];
}
void update(ll u, ll v, ll id)
{
    ll x = nchain[u][id], y = nchain[v][id];
    while(x != y)
    {
        ll up = top[x][id];
        pre[id].pb({d[up][id], d[u][id]});
        u = par[up][id];
        x = nchain[u][id];
    }
    pre[id].pb({d[v][id], d[u][id]});
}
void sol()
{
    cin >> n >> m;
    ll r1, r0;
    for(int i = 1; i<= n; i ++)
    {
        ll u, v;
        cin >> u >> v;
        if(u != 0)adj[u][0].pb(i);
        else r0 = i;
        if(v != 0)adj[v][1].pb(i);
        else r1 = i;
    }
    dfs(r0, 0, 0);
    dfs(r1, 0, 1);
    hld(r0, 0, 0);
    k = chain = 0;
    hld(r1, 0, 1);
    for(int i = 1; i <= m; i ++)
    {
        ll u, v;
        cin >> u >> v;
        ++a[d[u][0]][d[v][1]];
        //cout << d[u][0] <<" "<<d[v][1] << '\n';
    }
    //return;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            //cout << i <<" "<< j << endl;
            b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j];
            //cout << b[i][j] << ' ';
        }
        //cout << '\n';
    }
    for(int i = 1; i <= n; i ++)
    {
        pre[0].clear();
        pre[1].clear();
        ans = 0;
        update(i, r0, 0);
        update(i, r1, 1);
        for(pll x : pre[0])
        {
            for(pll y : pre[1])
            {
                ans += f(x.fi, y.fi, x.se, y.se);
                //cout << x.fi <<" "<<x.se << " " << y.fi <<" "<<y.se<<'\n';
            }
        }
        cout << ans << '\n';
    }
}
int main()
{
    if(fopen(task".inp", "r")){
       freopen(task".inp", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message (stderr)

spy.cpp: In function 'int main()':
spy.cpp:136:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  136 |        freopen(task".inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
spy.cpp:137:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  137 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
spy.cpp: In function 'void sol()':
spy.cpp:120:15: warning: 'r0' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |         update(i, r0, 0);
      |         ~~~~~~^~~~~~~~~~
spy.cpp:121:15: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |         update(i, r1, 1);
      |         ~~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70