QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #207800 | #6354. 4 | rsj | RE | 599ms | 26692kb | C++14 | 1.1kb | 2023-10-08 20:42:56 | 2023-10-08 20:42:56 |
Judging History
answer
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct edge {
int to;
edge *nex;
}*head[N];
void add(int u,int v) {
edge *cur=new edge;
cur->to=v;
cur->nex=head[u];
head[u]=cur;
}
int p[N],rk[N],in[N];
bool cmp(int a,int b) {
return in[a]<in[b];
}
unordered_map<int,int> grid[N];
int main() {
int n,M,i,j,k,u,v;
cin>>n>>M;
for(i=1;i<=M;i++) {
cin>>u>>v;
add(u,v),add(v,u);
grid[u][v]=grid[v][u]=1;
in[u]++,in[v]++;
}
for(i=1;i<=n;i++) p[i]=i;
sort(p+1,p+n+1);
for(i=1;i<=n;i++) rk[p[i]]=i;
long long ans=0;
for(i=1;i<=n;i++) {
u=p[i];
vector<int> to;
vector<pair<int,int>> e;
vector<bitset<500>> d;
for(edge *cur=head[u];cur;cur=cur->nex) {
if(rk[u]>rk[cur->to]) continue;
to.push_back(cur->to);
}
int m=to.size();
assert(m*m<2*M+10);
d.resize(m+3);
for(j=0;j<m;j++) for(k=j+1;k<m;k++) if(grid[to[j]][to[k]]) d[j][k]=d[k][j]=1,e.emplace_back(j,k);
for(auto x:e) {
tie(j,k)=x;
ans+=(d[j]&d[k]).count();
}
}
cout<<ans/3<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8884kb
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: 9644kb
input:
4 0
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 2ms
memory: 9524kb
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: 4ms
memory: 9772kb
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: 0
Accepted
time: 3ms
memory: 10300kb
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:
1094294
result:
ok 1 number(s): "1094294"
Test #6:
score: 0
Accepted
time: 580ms
memory: 25964kb
input:
447 99681 346 391 18 307 271 438 50 436 84 215 64 104 291 325 278 355 152 228 7 117 174 410 61 386 7 204 264 327 366 409 291 405 42 131 89 203 1 175 229 292 225 320 1 310 89 185 161 340 401 406 265 377 119 313 253 403 190 383 305 367 334 424 88 327 77 357 25 334 56 62 68 245 1 13 290 336 94 354 10 3...
output:
1641247665
result:
ok 1 number(s): "1641247665"
Test #7:
score: 0
Accepted
time: 599ms
memory: 26692kb
input:
447 99680 18 328 31 202 168 227 55 255 105 321 262 407 38 140 13 65 288 302 26 337 106 358 7 157 237 343 56 410 217 263 62 392 314 345 1 166 96 376 138 410 98 424 202 251 229 429 160 197 175 238 125 312 32 93 281 291 67 99 32 156 33 65 377 445 56 293 64 170 236 423 246 400 61 356 194 430 243 381 205...
output:
1641148875
result:
ok 1 number(s): "1641148875"
Test #8:
score: 0
Accepted
time: 564ms
memory: 26576kb
input:
447 99679 123 230 116 120 218 291 84 132 158 204 31 75 390 395 140 379 34 285 12 67 325 409 24 349 282 342 68 380 81 269 6 55 35 192 314 358 68 438 159 281 118 324 157 211 7 198 376 400 262 335 226 348 305 380 65 434 157 164 111 303 183 338 11 77 44 212 267 279 132 300 145 171 313 416 97 201 50 422 ...
output:
1641050086
result:
ok 1 number(s): "1641050086"
Test #9:
score: 0
Accepted
time: 570ms
memory: 25296kb
input:
447 99650 198 335 78 438 83 220 267 280 102 135 98 317 22 84 259 362 57 109 22 162 52 210 160 339 34 75 88 397 381 402 99 276 227 242 205 232 74 299 139 314 238 442 157 229 170 273 44 418 8 30 22 345 39 67 32 298 227 270 93 308 372 424 110 272 409 429 59 107 10 216 193 424 171 320 283 302 261 445 90...
output:
1638188297
result:
ok 1 number(s): "1638188297"
Test #10:
score: 0
Accepted
time: 597ms
memory: 25468kb
input:
447 99600 38 388 94 209 38 420 213 444 324 337 212 444 100 400 153 193 247 252 31 352 156 300 65 384 193 254 8 277 36 181 44 407 111 377 62 226 182 413 113 206 118 344 65 78 200 210 30 214 4 6 271 424 69 119 331 348 93 344 163 178 216 386 349 386 176 219 15 446 147 185 35 368 94 163 204 382 365 443 ...
output:
1633262630
result:
ok 1 number(s): "1633262630"
Test #11:
score: 0
Accepted
time: 574ms
memory: 26052kb
input:
447 99500 269 280 220 396 23 62 82 361 384 437 210 358 235 421 194 280 23 293 27 355 36 401 10 329 400 430 148 402 96 301 269 319 259 325 367 427 39 298 263 273 245 369 56 112 71 264 256 323 27 199 323 429 177 209 413 431 108 158 9 98 17 378 182 339 26 414 60 349 73 296 235 357 52 145 333 411 145 14...
output:
1623449253
result:
ok 1 number(s): "1623449253"
Test #12:
score: 0
Accepted
time: 591ms
memory: 25128kb
input:
447 99000 206 301 201 223 266 337 150 435 13 383 136 378 207 225 199 385 107 230 114 400 354 396 158 238 253 319 34 367 293 352 246 398 329 374 86 107 45 442 239 315 230 403 343 387 153 169 178 436 14 235 219 394 261 371 92 381 245 358 10 79 295 370 159 257 324 439 323 411 113 123 195 414 159 186 13...
output:
1575114565
result:
ok 1 number(s): "1575114565"
Test #13:
score: -100
Runtime Error
input:
447 98000 143 381 232 430 143 310 52 106 218 311 208 333 256 407 114 228 3 173 82 129 45 78 22 242 42 442 370 371 40 447 205 329 23 281 119 125 265 430 259 365 57 409 160 349 21 339 120 137 44 332 10 93 257 261 191 439 16 144 57 62 34 337 159 308 121 163 1 8 9 233 147 233 295 414 62 143 220 234 28 1...