QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#132894#4240. Tree Circlesparadoxica11yWA 188ms36264kbC++144.2kb2023-08-01 02:48:332023-08-01 02:48:39

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-01 02:48:39]
  • Judged
  • Verdict: WA
  • Time: 188ms
  • Memory: 36264kb
  • [2023-08-01 02:48:33]
  • Submitted

answer

// template by paradox & gege & parasat
#include <bits/stdc++.h>                                           
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
//using namespace __gnu_pbds;
 
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define se second
#define fi first
#define s second
#define f first
 
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef long double ld;
typedef long long ll;
 
//typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 300;
const pii base = mp(1e6 + 3, 1e6 + 7), mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, MOD = 998244353;
const ll INF = 1e18;
 
const int N = 3e5;
const int M = N + 7;
const int K = 1;

vector<int> bamboo[M], edges[M];
int par[M], pos[M];

int get_par(int v) {
    return v == par[v] ? v : par[v] = get_par(par[v]);
}

void merge(int v, int u, int val) {
    v = get_par(v);
    u = get_par(u);
    if (sz(bamboo[v]) < sz(bamboo[u]))
        swap(v, u);

    for (int x : bamboo[u])
        bamboo[v].pb(x);
    edges[v].pb(val);
    for (int x : edges[u])
        edges[v].pb(x);
    par[u] = v;
}

struct segment_tree {
    static const int TN = N;
    int g[TN << 2];

    void upd(int v) {
        g[v] = max(g[v << 1], g[v << 1 | 1]);
    }
    
    void build(const vector<int> &vals, int v = 1, int tl = 1, int tr = TN) {
        if (tl == tr) {
            g[v] = tl <= sz(vals) ? vals[tl - 1] : 0;
            return;
        }
        int tm = (tl + tr) >> 1;
        build(vals, v << 1, tl, tm);
        build(vals, v << 1 | 1, tm + 1, tr);
        upd(v);
    }

    int get(int l, int r, int v = 1, int tl = 1, int tr = TN) {
        if (l > r || tl > r || l > tr)
            return 0;
        if (l <= tl && tr <= r)
            return g[v];
        int tm = (tl + tr) >> 1;
        int le = get(l, r, v << 1, tl, tm);
        int ri = get(l, r, v << 1 | 1, tm + 1, tr);
        return max(le, ri);
    }
} t;

void solve() {
	int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        bamboo[i].pb(i);
    }

    for (int i = 1; i < n; i++) {
        int v, u;
        scanf("%d %d", &v, &u);
        merge(v, u, i);
    }

    int root = get_par(1);
    vector<int> &ord = bamboo[root];
    vector<int> &edg = edges[root];
    assert(sz(ord) == sz(edg) + 1);
    // cerr << "bamboo -> ";
    // for (int v : ord)
    //     cerr << v << " ";
    // cerr << " <-\n";
    // cerr << "edges -> ";
    // for (int x : edg) 
    //     cerr << x << " ";
    // cerr << " <-\n";
    t.build(edg);

    for (int i = 0; i < sz(ord); i++)
        pos[ord[i]] = i;

    int q;
    scanf("%d", &q);

    for (int i = 1; i <= q; i++) {
        int k;
        scanf("%d", &k);
        vector<int> ver;
        for (int j = 1; j <= k; j++) {
            int v;
            scanf("%d", &v);
            ver.pb(v);
        }
        sort(all(ver), [&](const int &v, const int &u) {
            return pos[v] < pos[u];
        });

        vector<int> vals;
        for (int i = 1; i < sz(ver); i++) {
            int l = pos[ver[i - 1]], r = pos[ver[i]];
            int val = t.get(l + 1, r);
            if (!vals.empty())
                vals.back() = min(vals.back(), val);
            else
                vals.pb(val);
            vals.pb(val);
        }

        // cerr << "r :: ";
        // for (int x : vals) 
        //     cerr << x << ' ';
        // cerr << " *\n";

        int ans = 1;
        for (int x : vals)
            ans = 1ll * ans * x % MOD;

        printf("%d\n", ans);
    }
    
}
 
int main() {
	int TT;
	TT = 1;
	// scanf("%d", &TT);
	for (int tt = 1; tt <= TT; ++tt) {
		solve();
	}
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 24816kb

input:

3
1 2
2 3
2
3 1 2 3
2 1 3

output:

2
4

result:

ok 2 number(s): "2 4"

Test #2:

score: 0
Accepted
time: 60ms
memory: 24864kb

input:

1000
251 1
610 251
1 621
610 534
617 1
27 617
54 534
251 435
610 984
1 850
291 610
251 461
51 27
376 617
461 310
36 850
36 351
456 461
461 171
456 294
949 294
688 1
833 610
174 534
435 841
841 60
556 251
251 423
655 376
688 188
610 448
456 549
894 841
65 688
65 522
421 435
382 65
894 613
617 789
880...

output:

275623202
374067774
494473471
420011499
643061355
554361044
755532440
289845686
45368764
527834219
925520205
659238238
433870012
469990636
657873561
852213216
966862980
542663190
982471669
458857532
478701698
947460452
451178245
603042191
422792889
685952031
417241570
548357718
223143158
101179924
9...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 5ms
memory: 24844kb

input:

2000
1 1229
1229 743
7 1229
7 1684
293 1
1652 293
1458 743
293 1912
1912 1726
359 1458
372 743
772 293
756 1
409 1726
1652 921
433 1912
359 1515
1458 1897
1458 1439
409 952
1439 1877
1298 756
743 1055
1665 1897
1313 743
743 978
1515 1099
627 409
1665 1318
921 1859
293 39
627 1954
1665 646
1055 1584
...

output:

985661081
289663642
426379198
961782139
145012705
45028730
513933554
853668549
529541313
702845230

result:

ok 10 numbers

Test #4:

score: -100
Wrong Answer
time: 188ms
memory: 36264kb

input:

300000
1 265092
1 46487
265092 220364
124925 1
1 288590
265092 156898
280571 46487
184789 220364
280571 151321
280571 66880
86168 151321
151321 273555
46487 112431
124925 45049
1 66769
112431 36492
86168 137565
251083 66880
143467 66880
284087 1
280571 112916
112431 254872
238475 280571
180865 36492...

output:

425265333
650921663
28695301
191498362
567238295
582516091
948253770
242063171
597569966
190082202
1
521207503
1
570927982
122195019
889056495
982165169
1
70088500
224396729
443558073
770844475
992420728
129019298
66932621
140351691
402404024
748029355
324810833
847382658
975494158
238329979
4835401...

result:

wrong answer 11th numbers differ - expected: '300000', found: '1'