QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187898#6561. Fail FastFeet_McYeetWA 2ms10620kbC++173.4kb2023-09-25 05:07:482023-09-25 05:07:49

Judging History

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

  • [2023-09-25 05:07:49]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10620kb
  • [2023-09-25 05:07:48]
  • 提交

answer

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <iterator>
#include <algorithm>
// #include <bit>
#include <numeric>
#include <iomanip>
#include <stack>
using namespace std;
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
#define el << '\n'
#define nl cout << '\n'
#define cina(a,n) for (int i=0; i<n; i++) cin >> a[i]
#define ll long long
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define pb push_back
#define ansyes cout << "YES\n"
#define ansno cout << "NO\n"
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pss pair<short, short>
#define MAX *max_element
#define MIN *min_element
#define rsz resize
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define bsi(x, v) (int) (lower_bound(x.begin(), x.end(), v) - x.begin());
const int inf = 1000000000;
const ll inf2 = 4000000000000000000;

const int MAXN = 100005;

struct node {
    double c;
    double p;
    int o;
};

bool operator < (const node& n1, const node& n2) {
    return n1.c*(1-n2.p) > n2.c*(1-n1.p);
}

bool operator != (const node& n1, const node& n2) {
    return !(n1.c==n2.c && n1.p==n2.p && n1.o==n2.o);
}

int par[MAXN];
int dep[MAXN];

void join(int a, int b) {
    if (dep[a]>dep[b]) swap(a,b);
    par[b] = a;
}

int g(int cn) {
    if (par[cn] == cn) return cn;
    par[cn] = g(par[cn]);
    return par[cn];
}

int p[MAXN];
vector<int> ch[MAXN];
vector<int> cm[MAXN];
vector<int> cdm[MAXN];

void dfs(int cn, int d) {
    dep[cn] = d;
    for (int i : ch[cn]) dfs(i, d+1);
}

node re[MAXN];

priority_queue<node> pq;

void dfs2(int cn) {
    cout << cn+1 el;
    for (int i : cdm[cn]) {
        pq.push(re[i]);
    }
    for (int i : cm[cn]) {
        dfs2(i);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    forn(i,n) {
        par[i] = i;
    }
    forn(i,n) {
        cin >> re[i].c >> re[i].p >> p[i];
        p[i]--;
        re[i].o = i;
        pq.push(re[i]);
        if (p[i] != -1) ch[p[i]].pb(i);
    }
    forn(i,n) if (p[i]==-1) dfs(i, 0);
    while (sz(pq)) {
        // cout << sz(pq) << endl;
        node temp = pq.top();
        pq.pop();
        if (re[temp.o] != temp) continue;
        if (p[temp.o] == -1) continue;
        int pa = g(p[temp.o]);
        if (temp < re[pa]) {
            re[pa].c += re[pa].p * temp.c;
            re[pa].p *= temp.p;
            cm[p[temp.o]].pb(temp.o);
            pq.push(re[pa]);
            join(pa, temp.o);
        }
    }
    forn(i,n) {
        vector<int> temp;
        temp.rsz(sz(cm[i]));
        forn(j,sz(cm[i])) temp[j] = cm[i][j];
        sort(all(temp));
        sort(all(ch[i]));
        int a = 0, b = 0 ;
        forn(k, sz(temp)+sz(ch[i])) {
            if (b == sz(temp)) {
                cdm[i].pb(ch[i][a]);
                a++;
                continue;
            }
            if (ch[i][a] == temp[b]) {
                a++; b++; k++;
                continue;
            }
            cdm[i].pb(ch[i][a]);
            a++; 

        }
    }
    forn(i,n) if (p[i]==-1) pq.push(re[i]);
    while (sz(pq)) {
        int temp = pq.top().o;
        pq.pop();
        dfs2(temp);
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 10620kb

input:

4
100 0.5 0
200 0.1 1
10 0.5 2
10 0.9 0

output:

4
1
2
3

result:

ok correct

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 10616kb

input:

4
84 0.716 0
91 0.115 0
19 0.640 1
103 0.455 0

output:

2
4
1
3

result:

wrong answer your plan is not optimal