QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#329340 | #6292. 最小公倍数 | junbin | 50 | 1229ms | 10252kb | C++14 | 4.1kb | 2024-02-16 16:15:16 | 2024-02-16 16:15:18 |
Judging History
answer
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <list>
#include<fstream>
#include <bitset>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define pb push_back
#define P pair
#define V vector
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FFOR(i, a, b) for (int i = a; i <= b; ++i)
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;}
out << "]";
return out;
}
const int N = 50000 + 10, M = 1e5 + 10;
bool ans[N];
struct E {
int u, v, a, b;
} e[M];
struct Q {
int u, v, a, b, i;
bool operator< (const Q& other) {
return b < other.b;
}
} q[N];
bool comp1(E& e1, E& e2) {
return e1.a < e2.a;
}
bool comp2(E& e1, E& e2) {
return e1.b < e2.b;
}
//DSU
struct Node {
int fax, fay, w, a, b;
};
vector<Node> stk;
int p[N], rk[N], maxa[N], maxb[N];
int top = 0;
int find(int x) {
if (p[x] != x) return find(p[x]);
return p[x];
}
bool merge(int u, int v, int a, int b) {
int fax = find(u), fay = find(v);
if(rk[fax] > rk[fay]) {
swap(fax, fay);
}
top++;
stk.push_back({fax, fay, rk[fax] == rk[fay], maxa[fay], maxb[fay]});
maxa[fay] = max(maxa[fay], a);
maxb[fay] = max(maxb[fay], b);
if(fax != fay) {
p[fax] = fay;
maxa[fay] = max(maxa[fay], maxa[fax]);
maxb[fay] = max(maxb[fay], maxb[fax]);
if(rk[fay] == rk[fax]) rk[fay]++;
return true;
}
return false;
}
void undo() {
while(top--) {
auto pa = stk.back(); stk.pop_back();
int fax = pa.fax, fay = pa.fay, w = pa.w, a = pa.a, b = pa.b;
p[fax] = fax;
rk[fay] -= w;
maxa[fay] = a;
maxb[fay] = b;
}
}
void init() {
stk.clear();
memset(rk, 0, sizeof rk);
for(int i = 0; i < N; i++) p[i] = i, maxa[i] = maxb[i] = -1;
}
void solve() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
int u, v, a, b;
scanf("%d%d%d%d", &u, &v, &a, &b);
e[i] = {u, v, a, b};
}
sort(e, e + m, comp1);
int k;
scanf("%d", &k);
for(int i = 0; i < k; i++) {
int u, v, a, b;
scanf("%d%d%d%d", &u, &v, &a, &b);
q[i] = {u, v, a, b, i};
}
sort(q, q + k);
//分块范围初始化
int s = sqrt(m);
vector<pair<int, int>> blocks;
for(int i = 0; i < m; i += s) {
blocks.push_back({i, min(m - 1, i + s - 1)});
}
vector<vector<int>> T(blocks.size());
for(int i = 0; i < k; i++) {
int j = 0;
while(j < blocks.size() && e[blocks[j].second].a <= q[i].a) j++;
T[min(j, (int)(T.size() - 1))].push_back(i);
}
//for(int i = 0; i < T.size(); i++) {
//cout << i << " " << blocks[i].first << " " << blocks[i].second << T[i] << endl;
//}
for(int i = 0; i < blocks.size(); i++) {
int l = blocks[i].first, r = blocks[i].second;
init();
sort(e, e + l, comp2);
int j = 0;
for(int x : T[i]) {
int u = q[x].u, v = q[x].v, a = q[x].a, b = q[x].b, idx = q[x].i;
while(j < l && e[j].b <= b) {
merge(e[j].u, e[j].v, e[j].a, e[j].b);
j++;
}
//处理当前分块
top = 0;
for(int o = l; o <= r; o++) {
if(e[o].a <= a && e[o].b <= b) {
merge(e[o].u, e[o].v, e[o].a, e[o].b);
}
}
int fau = find(u), fav = find(v);
if(fau == fav && maxa[fau] == a && maxb[fau] == b) {
ans[idx] = true;
}
undo();
}
}
for(int i = 0; i < k; i++) {
if(ans[i]) printf("Yes\n");
else printf("No\n");
}
}
int main() {
int t = 1;
while(t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 10
Accepted
time: 0ms
memory: 6576kb
input:
1000 999 1 2 225797523 891449793 2 3 755166876 396261217 3 4 999 303780774 4 5 808505152 999 5 6 755166876 999 6 7 775257063 999 7 8 372442657 661952609 8 9 999 396261217 9 10 999 999 10 11 999 891449793 11 12 999 999 12 13 945532180 331536022 13 14 755166876 391084640 14 15 472712245 551316159 15 1...
output:
Yes No No No Yes No No Yes No No Yes No No Yes No No No Yes No Yes No No Yes No No No Yes No Yes Yes No Yes No Yes Yes No No No No Yes No Yes Yes Yes No No Yes No Yes Yes Yes No No No No Yes Yes Yes No No No No No Yes Yes No Yes Yes Yes Yes Yes No No No Yes Yes No Yes Yes Yes Yes Yes Yes Yes No Yes ...
result:
ok 1000 lines
Test #2:
score: 10
Accepted
time: 4ms
memory: 6604kb
input:
1000 2000 296 955 69349222 960716415 85 616 560280696 590872653 608 731 2000 624240497 711 457 69349222 546570491 795 712 465431029 587460957 108 185 69349222 2000 658 241 69349222 624240497 775 145 2000 2000 521 809 560280696 680453406 908 748 560280696 565475559 661 790 560280696 620034060 97 241 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes No Yes Yes Yes Yes No Yes Yes Yes Yes No Yes Yes Yes No Yes No Yes Yes No Yes No Yes No Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes No No Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Ye...
result:
ok 1000 lines
Test #3:
score: 10
Accepted
time: 274ms
memory: 7980kb
input:
50000 49999 1 2 49999 49999 2 3 398978075 485060875 3 4 200717706 575788167 4 5 49999 49999 5 6 517220748 49999 6 7 49999 49999 7 8 379648860 485060875 8 9 767094950 49999 9 10 517220748 49999 10 11 330793410 49999 11 12 658108139 363197497 12 13 517220748 49999 13 14 237748367 49999 14 15 429477754...
output:
Yes Yes Yes No Yes Yes No No No Yes Yes No No Yes Yes No Yes Yes Yes Yes Yes Yes Yes No Yes No No Yes Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes Yes Yes Yes No Yes ...
result:
ok 50000 lines
Test #4:
score: 10
Accepted
time: 288ms
memory: 7336kb
input:
50000 49999 1 2 49999 49999 2 3 80068996 579565654 3 4 891497929 637414542 4 5 49999 49999 5 6 728937744 49999 6 7 49999 49999 7 8 817501744 579565654 8 9 660562486 49999 9 10 728937744 49999 10 11 891984225 49999 11 12 567422834 921607632 12 13 728937744 49999 13 14 60385715 49999 14 15 356537986 9...
output:
No Yes Yes No Yes Yes No No Yes No No Yes Yes No Yes Yes No Yes Yes Yes No No Yes Yes Yes Yes No Yes Yes Yes No Yes Yes Yes Yes Yes Yes No No No Yes Yes No Yes No Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes No No Yes Yes No Yes Yes Yes No No Yes Yes Yes Yes No Yes No Yes...
result:
ok 50000 lines
Test #5:
score: 10
Accepted
time: 1229ms
memory: 10252kb
input:
50000 100000 31845 44471 29 6 42887 14451 29 1 35834 40871 9 8 27013 40036 15 27 25431 12281 6 9 38473 1539 22 11 3935 10264 13 12 30495 44816 14 29 28680 6984 27 8 45982 17489 11 18 20944 32376 1 20 48011 31604 23 17 7945 31125 0 7 19269 27801 21 15 26103 15233 18 14 3318 39002 4 19 7169 42372 15 1...
output:
Yes Yes No Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes No No Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes No No No Yes Yes Yes Yes Yes Yes No No No Yes No Yes Yes Yes Yes No Yes No Yes Yes No Yes Yes Yes Yes No Yes Yes Yes No Yes Yes No Yes No No ...
result:
ok 50000 lines
Test #6:
score: 0
Time Limit Exceeded
input:
50000 100000 46670 24272 0 779825528 14775 11795 0 262184992 36534 25057 0 111471209 17613 37731 0 658757908 17673 281 0 765932268 896 1812 0 130329112 21061 4133 0 111471209 37088 34393 0 658757908 24840 15079 0 100000 15614 24426 0 100000 25874 38296 0 100000 41454 29879 0 743034123 7609 35953 0 1...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
50000 100000 44493 32633 888404736 100000 5302 20812 388289098 903704326 14664 16522 999073361 557317767 29199 49724 362436467 100000 30999 37957 998356811 100000 43627 6338 860319212 903704326 30793 45647 999073361 100000 34756 33707 362436467 903704326 40687 27020 100000 303932288 10772 8358 10000...
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
50000 100000 9158 24068 548036850 100000 36234 19571 337550348 421837264 30325 9327 577788435 461881000 15475 25956 820269847 100000 33633 36935 206377175 100000 30116 38126 913914941 421837264 41188 16618 577788435 100000 46668 4690 820269847 421837264 27581 20933 100000 714367582 39244 2141 100000...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
50000 100000 40176 49150 207668964 100000 33519 18330 286811598 939970203 45986 2132 156503509 366444233 18104 18541 278103226 100000 2620 2266 414397540 100000 16605 3561 114994314 939970203 17936 37589 156503509 100000 8580 9320 278103226 939970203 14475 14846 100000 977319231 17716 29571 100000 1...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
50000 100000 13903 49885 463731817 100000 22632 45601 412915704 32299587 33579 38348 896622016 640681538 3166 33366 129265430 100000 2403 44873 646822083 100000 17232 28497 844984414 32299587 15818 9473 896622016 100000 31405 21442 129265430 32299587 11318 40672 100000 209560531 46090 32595 100000 1...