| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 374928 |
2021-03-08T14:50:44 Z |
Killer2501 |
스파이 (JOI13_spy) |
C++14 |
|
190 ms |
66944 KB |
#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
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);
| ~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1772 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2028 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2028 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 9 |
Correct |
1 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
38764 KB |
Output is correct |
| 2 |
Correct |
37 ms |
32492 KB |
Output is correct |
| 3 |
Correct |
37 ms |
35692 KB |
Output is correct |
| 4 |
Correct |
39 ms |
34540 KB |
Output is correct |
| 5 |
Correct |
39 ms |
38508 KB |
Output is correct |
| 6 |
Correct |
37 ms |
32536 KB |
Output is correct |
| 7 |
Correct |
39 ms |
39532 KB |
Output is correct |
| 8 |
Correct |
40 ms |
39404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
64236 KB |
Output is correct |
| 2 |
Correct |
118 ms |
35948 KB |
Output is correct |
| 3 |
Correct |
148 ms |
49300 KB |
Output is correct |
| 4 |
Correct |
139 ms |
66284 KB |
Output is correct |
| 5 |
Correct |
151 ms |
55916 KB |
Output is correct |
| 6 |
Correct |
127 ms |
36724 KB |
Output is correct |
| 7 |
Correct |
190 ms |
66944 KB |
Output is correct |
| 8 |
Correct |
190 ms |
66668 KB |
Output is correct |
