oj.uz

Submission #764888

# Submission time Handle Problem Language Result Execution time Memory
764888 2023-06-24T06:18:25 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 1000 ms 57700 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ent '\n'
#define all(x) x.begin(), x.end()
#define s second
#define f first
#define pb push_back
typedef long long ll;
using namespace std;
const int maxn = 2e6 + 250;
const int mod = 1e9 + 7;
const int K = 400;
const double Pi = acos(-1.0);
const long double eps = 1e-9;
#define int long long
int a[maxn], f[maxn];
pair<int,int>p[maxn];
vector<pair<int,int>>g[maxn];
map<pair<int,int>,int>mp;
void dfs(int v, int pa = 0) {
    for(auto to:g[v]) {
        if(to.f==pa)continue;
        p[to.f] = {v, to.s};
        dfs(to.f, v);
    }
}
void chek(int a) {
    int sum = 0;
    while(a!=0) {
        f[mp[{p[a].f, a}]] = p[a].s;
        a = p[a].f;
    }
}
void solve() {
    int n, k, sum = 0;
    cin >> n;
    for(int i = 1;i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u++,v++;
        g[u].pb({v, w});
        g[v].pb({u, w});
        mp[{u,v}]=i;
        mp[{v,u}]=i;
    }
    p[1] = {0, 0};
    dfs(1);
    cin >> k;
    for(int i = 1;i <= k; i++) {
        int a, b, c, d, e, sum = 0;
        cin >> a >> b >> c >> d >> e;
        chek(a+1);
        chek(b+1);
        chek(c+1);
        chek(d+1);
        chek(e+1);
        for(int j = 1;j <= n; j++) {
            sum += f[j];
            f[j] = 0;
        }
        cout << sum << ent;
    }
}
signed main () {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("position.in", "r" , stdin);
    // freopen("position.out", "w", stdout);
    int t = 1;
    // cin >> t;
    for(int i = 1;i <= t; i++) {
        // cout << "Case #" << i << ": ";
        solve();    
    }
}

Compilation message

roadsideadverts.cpp: In function 'void chek(long long int)':
roadsideadverts.cpp:29:9: warning: unused variable 'sum' [-Wunused-variable]
   29 |     int sum = 0;
      |         ^~~
roadsideadverts.cpp: In function 'void solve()':
roadsideadverts.cpp:36:15: warning: unused variable 'sum' [-Wunused-variable]
   36 |     int n, k, sum = 0;
      |               ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 57700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 57280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Execution timed out 1086 ms 57700 KB Time limit exceeded
3 Halted 0 ms 0 KB -