QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#243451 | #6354. 4 | Zeardoe | WA | 5ms | 8804kb | C++20 | 2.9kb | 2023-11-08 12:06:10 | 2023-11-08 12:06:10 |
Judging History
answer
/*
[templates]:
duipai
spjdp
compre
addhis
floor_sum
treedfs
matrix
network_flow
polynomial
lca
bitset
valuesgt
fenwick
erbitree
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e18;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0));
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; }
reverse(s.begin(), s.end()); cerr << s << endl;
return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍!
//use std::array.
const int N = 100000, sq = sqrt(2 * N);
vector<int> edge[N + 10], rgt[N + 10]; int deg[N + 10]; int rnk[N + 10]; pii e[N + 10];
bool can[N + 10]; int rernk[N + 10]; pii ree[N + 10]; bitset<sq + 5> bs[sq + 5];
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//freopen();
//freopen();
//time_t start = clock();
//think twice,code once.
//think once,debug forever.
int n, m; cin >> n >> m;
f(i, 1, m) {
int u, v; cin >> u >> v; deg[u] ++; deg[v] ++; e[i] = {u, v};
}
vector<pii> vec;
f(i, 1, n) vec.push_back({deg[i], i});
sort(vec.begin(), vec.end());
f(i, 0, n - 1) rnk[vec[i].second] = i + 1;
f(i, 1, m) {
int u = rnk[e[i].first], v = rnk[e[i].second];
// cerr << "First Relabel: edge: " << u << " " << v << endl;
edge[u].push_back(v); edge[v].push_back(u);
if(u > v) swap(u, v);
rgt[u].push_back(v);
}
int ans = 0;
f(i, 1, n) {
int cnt = 0;
for(int j : rgt[i]) rernk[j] = ++cnt;
for(int j : rgt[i]) {
for(int k : rgt[j]) {
if(rernk[k]) {
ree[++ cnt] = {rernk[j], rernk[k]};
bs[rernk[j]][rernk[k]] = bs[rernk[k]][rernk[j]] = 1;
}
}
}
int tmp = 0;
f(j, 1, cnt) {
int x = ree[j].first, y = ree[j].second;
tmp += (bs[x] & bs[y]).count();
}
ans += tmp / 3;
f(j, 1, cnt) bs[j].reset();
for(int j : rgt[i]) rernk[j] = 0;
}
cout << ans << endl;
//time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8236kb
input:
5 9 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 8160kb
input:
4 0
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 3ms
memory: 8324kb
input:
50 50 28 35 12 24 31 50 10 24 21 44 5 31 23 36 31 45 6 39 4 8 13 37 42 48 17 45 19 33 12 21 19 32 16 43 12 47 25 31 40 48 8 49 43 48 6 42 27 34 13 39 17 40 13 35 3 49 20 24 5 12 43 44 15 37 24 27 8 43 4 22 17 38 28 47 29 46 3 15 9 49 1 41 43 45 3 6 37 48 13 30 11 43 8 25 33 38 16 32 32 41
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 5ms
memory: 8804kb
input:
100 4900 64 78 3 13 93 96 48 64 34 64 5 76 66 74 44 78 17 20 30 73 5 34 24 100 23 65 4 70 22 95 47 70 6 89 15 70 70 82 88 90 29 80 27 64 16 59 28 99 67 68 85 99 37 85 8 46 71 78 40 95 6 21 27 66 16 89 11 83 17 57 19 36 21 70 27 86 27 45 5 56 10 64 23 33 87 91 37 40 21 55 75 79 54 96 3 77 70 78 36 93...
output:
3689634
result:
ok 1 number(s): "3689634"
Test #5:
score: -100
Wrong Answer
time: 4ms
memory: 8664kb
input:
100 4000 73 78 38 98 9 65 43 72 20 47 6 37 49 60 48 87 48 77 23 100 57 59 42 99 40 88 20 96 19 44 35 80 12 93 34 44 63 75 3 49 32 99 47 61 3 13 54 81 55 96 16 74 28 77 43 45 25 92 5 82 3 83 9 55 64 78 39 89 19 64 58 75 1 18 22 76 16 55 18 60 14 55 29 96 37 97 26 97 11 53 24 79 7 35 53 54 31 74 31 32...
output:
1094346
result:
wrong answer 1st numbers differ - expected: '1094294', found: '1094346'