# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
821029 | danikoynov | Marshmallow Molecules (CCO19_day2problem2) | C++14 | 3 ms | 596 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 5010 + 1;
int n, m;
vector < int > adj[maxn];
bitset < maxn > edge[maxn];
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++)
{
int a, b;
cin >> a >> b;
edge[a][b] = 1;
adj[a].push_back(b);
}
int ans = 0;
bitset < maxn > cur, op;
for (int i = n; i > 0; i --)
{
sort(adj[i].begin(), adj[i].end());
cur = edge[i];
for (int j = 0; j < adj[i].size(); j ++)
{
int v = adj[i][j];
cur |= edge[v];
edge[v] = cur;
}
/**for (int j = i + 1; j <= n; j ++)
{
if (edge[i][j] == 1)
{
edge[j] |= edge[i];
}
}*/
}
bitset < maxn > zero;
for (int i = n; i > 0; i --)
{
edge[i] &= zero;
zero[i] = 1;
}
for (int i = 1; i <= n; i ++)
{
edge[i][i] = 0;
ans += edge[i].count();
}
/**for (int i = 1; i <= n; i ++, cout << endl)
for (int j = 1; j <= n; j ++)
cout << edge[i][j] << " ";*/
cout << ans << endl;
}
int main()
{
solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |