QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#374772 | #3719. Dynamic Graph | ucup-team1251 | TL | 0ms | 0kb | C++20 | 3.3kb | 2024-04-02 17:59:13 | 2024-04-02 17:59:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<ll, int>
typedef unsigned long long ull;
const int N = 300 + 5;
int n, m, q, cnt;
inline char gtc()
{
static char BB[10000000], * S = BB, * T = BB;
return S == T && (T = (S = BB) + fread(BB, 1, 10000000, stdin), S == T) ? EOF : *S++;
}
inline int read()
{
int x = 0, f = 1;
char ch = gtc();
if(ch == EOF)
return EOF;
while(ch < '0' || ch > '9')
{
if(ch == '-')
f = -1;
ch = gtc();
}
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ 48), ch = gtc();
return x * f;
}
struct CT
{
ull ct[5];
CT()
{
ct[0] = ct[1] = ct[2] = ct[3] = ct[4] = 0;
}
CT(int x)
{
ct[0] = ct[1] = ct[2] = ct[3] = ct[4] = 0;
set(x);
}
void clear()
{
ct[0] = ct[1] = ct[2] = ct[3] = ct[4] = 0;
}
void set(int p)
{
int x = p % 64;
ull pt = 1ULL << x;
ct[p / 64] |= pt;
}
int cnt()const
{
int ret = 0;
for(int i = 0; i < 5; i++)
{
ull x = ct[i];
while(x > 0)
{
if(x & 1)
ret++;
x >>= 1;
}
}
return ret;
}
CT operator+(const CT& y)
{
CT ret;
for(int i = 0; i < 5; i++)
ret.ct[i] = ct[i] | y.ct[i];
return ret;
}
};
CT cctv[305];
void solve()
{
n = read();
if(n == EOF)
return;
m = read(), q = read();
vector<bool> vis(n + 2);
vector<int> degr(n + 2), last(n + 2), p(n + 2), h(n + 2);
vector<int> mp[n + 1];
function<void(int, CT)> dfs = [&](int u, CT xx)
{
xx.set(u);
cctv[u] = cctv[u] + xx;
for(auto to : mp[u])
{
last[to]--;
if(vis[to]) last[to] = 0;
if(last[to] == 0 && vis[to]) p[++cnt] = to;
if(!vis[to]) dfs(to, xx);
}
};
for(int i = 1; i <= m; i++)
{
int u, v;
u = read(), v = read();
mp[u].push_back(v);
degr[v]++;
}
int idx = 0;
for(int i = 1; i <= n; i++)
{
if(degr[i] == 0) h[++idx] = i;
}
while(q--)
{
int x;
x = read();
vis[x] = 1 - vis[x];
cnt = idx;
last = degr;
for(int i = 1; i <= n; i++)
{
cctv[i].clear();
}
p = h;
while(cnt)
{
int u = p[cnt--];
if(vis[u] == 1)
{
for(auto to : mp[u])
{
last[to]--;
if(vis[to]) last[to] = 0;
if(last[to] == 0)
{
p[++cnt] = to;
}
}
}
else
{
CT qm;
dfs(u, qm);
}
}
ll ans = 0;
for(int i = 1; i <= n; i++)
{
if(!vis[i])
ans += cctv[i].cnt() - 1;
}
printf("%d\n", ans);
}
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int t = 1;
//cin >> t;
while(t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
300 38355 300 169 195 236 244 38 42 205 297 8 50 1 149 170 255 81 123 80 81 78 140 60 88 9 97 253 288 132 170 167 253 18 83 7 32 153 203 4 44 156 159 178 185 2 267 278 297 234 251 50 221 42 222 88 289 130 142 117 254 44 60 120 207 104 167 139 296 175 273 98 253 164 200 23 211 33 260 109 176 17 233 3...