QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#329347#6292. 最小公倍数junbin50 1241ms9724kbC++144.1kb2024-02-16 16:17:482024-02-16 16:17:48

Judging History

你现在查看的是最新测评结果

  • [2024-02-16 16:17:48]
  • 评测
  • 测评结果:50
  • 用时:1241ms
  • 内存:9724kb
  • [2024-02-16 16:17:48]
  • 提交

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();
  for(int i = 0; i < N; i++) p[i] = i, maxa[i] = maxb[i] = -1, rk[i] = 0;
}


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: 2ms
memory: 4604kb

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: 0ms
memory: 4608kb

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: 277ms
memory: 7320kb

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: 293ms
memory: 7304kb

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: 1241ms
memory: 9724kb

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...

output:


result: