oj.uz

Submission #341973

# Submission time Handle Problem Language Result Execution time Memory
341973 2020-12-31T20:16:31 Z Hazem Deblo (COCI18_deblo) C++14
45 / 90
 1000 ms 27756 KB 
/*
ID: tmhazem1
LANG: C++14
TASK: pprime
*/

#include <bits/stdc++.h>
using namespace std;

#define S second
#define F first
#define LL long long

const int N = 2e5+10;


LL LINF = 100000000000000000;
LL INF = 1000000000;
int MOD = 1e9+7;

int vals[N],par[N][30],depth[N];
LL pr[N];
vector<int>adj[N];

void dfs(int i,int pre){

    pr[i] = pr[pre]^vals[i];
    par[i][0] = pre;
    for(int j=1;j<=20;j++)
        par[i][j] = par[par[i][j-1]][j-1];

    for(auto x:adj[i])
        if(x!=pre)depth[x] = depth[i]+1,dfs(x,i);
}

int lca(int u,int v){

    if(depth[u]<depth[v])swap(u,v);

    for(int i=20;i>=0;i--)
        if(depth[u]-(1<<i)>=depth[v])
            u = par[u][i];

    if(u==v)return u;

    for(int i=20;i>=0;i--)
        if(par[u][i]!=par[v][i])
            u = par[u][i],v = par[v][i];

    return par[u][0];
}

int main()
{
    // freopen("out.txt","w",stdout);
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
        scanf("%d",&vals[i]);

    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1,1);
    LL ans = 0;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            ans += pr[i]^pr[j]^vals[lca(i,j)];

    printf("%lld\n",ans);
}

Compilation message

deblo.cpp: In function 'int main()':
deblo.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
deblo.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |         scanf("%d",&vals[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
deblo.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
45.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct
4 Correct 46 ms 5228 KB Output is correct
5 Correct 51 ms 5228 KB Output is correct
6 Execution timed out 1041 ms 27756 KB Time limit exceeded
7 Execution timed out 1086 ms 27756 KB Time limit exceeded
8 Execution timed out 1092 ms 22636 KB Time limit exceeded
9 Execution timed out 1085 ms 22124 KB Time limit exceeded
10 Execution timed out 1090 ms 21612 KB Time limit exceeded