제출 #1163201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163201		modwwe	City Mapping (NOI18_citymapping)	C++20	71.11 / 100	20 ms	10824 KiB

citymapping

#include "citymapping.h"
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1tst"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf=1e18;
const int mod2 = 1e9+7;
//const int base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en;
ll kk;
ll el = 19;/*
main()
{
    ///top1tst
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    ///top1tst
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    ///top1tst
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
//   cin>>s1;
    // int t;cin>>t;while(t--)
    phongbeo();
    checktime
    ///top1tst
}
static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
static long long dist[1005];
static vector< pair<int, int> > adjlist[1005];
static vector< pair< pair<int, int>, int > > edgelist, user_edgelist;

static void dfs(int x, int p, long long d, int dep)
{
    dist[x] = d;
    depth[x] = dep;
    twok[x][0] = p;
    for (int i = 1; i <= 10; i++)
    {
        if (twok[x][i - 1] == -1) break;
        twok[x][i] = twok[twok[x][i - 1]][i - 1];
    }
    for (int i = 0; i < (int)adjlist[x].size(); i++)
    {
        if (adjlist[x][i].first == p) continue;
        dfs(adjlist[x][i].first, x, d + adjlist[x][i].second, dep + 1);
    }
}

static int lca(int x, int y)
{
    if (depth[x] > depth[y]) swap(x, y);
    int dd = depth[y] - depth[x];
    for (int i = 0; i <= 10; i++) if (dd & (1 << i)) y = twok[y][i];
    if (x == y) return x;
    for (int i = 10; i >= 0; i--)
    {
        if (twok[x][i] != twok[y][i])
        {
            x = twok[x][i];
            y = twok[y][i];
        }
    }
    return twok[x][0];
}
long long get_distance(int X, int Y)
{
    if (X <= 0 || X > N || Y <= 0 || Y > N)
    {
        printf("Wrong Answer: get_distance() arguments out of range.\n");
        exit(0);
    }
    curQ++;
    if (curQ > Q)
    {
        printf("Wrong Answer: Too many calls to get_distance().\n");
        exit(0);
    }
    return dist[X-1] + dist[Y-1] - dist[lca(X-1, Y-1)] * 2;
}*/
ll dp[1001][1001];
ll get(int x,int y)
{
    if(x==y) return 0;
    if(dp[x][y]==-1)dp[x][y]=dp[y][x]=get_distance(x,y);
    return dp[x][y];
}
bool cmp(int a,int b)
{
    return get(1,a)<get(1,b);
}
int heavy[100001];
bool nouse[1001];
vector<int> v[100001];
int dfs(int x,int y)
{
    int mxz=0,sz=1;
    heavy[x]=0;
    for(auto f:v[x])
        if(!nouse[f])
        {
            int s=dfs(f,x);
            sz+=s;
            if(s>mxz)
                mxz=s,heavy[x]=f;
        }
    return sz;
}
void find_roads(int n, int q, int a[], int b[], int cost[])
{
    vector<int> vv;
    for(int i=2; i<=n; i++)
        vv.pb(i);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            dp[i][j]=-1;
    sort(vv.begin(),vv.end(),cmp);
    for(auto x:vv)
    {
        memset(nouse,0,sizeof nouse);
        dem2=0;
        dem3++;
        while(true)
        {
            dfs(1,0);
            s2=1;
            vector<int>hld;
            while(s2!=0)hld.pb(s2),s2=heavy[s2];
            dem2++;
            if(v[hld.back()].size()!=0)
            {
                v[hld.back()].pb(x);
                a[dem]=hld.back();
                b[dem]=x;
                cost[dem]=get(1,x)-get(1,hld.back());
                dem++;
                break;
            }
            ll xx=(get(1,hld.back())+get(1,x)-get(hld.back(),x))/2;
            bool de=0;
            while(true)
            {
                if(hld.size()==0)assert(0);
                if(get(1,hld.back())!=xx)
                {
                    nouse[hld.back()]=1;
                    hld.pop_back();
                }
                else
                {
                    if(v[hld.back()].size()==0)
                    {
                        s3=hld.back();
                        v[hld.back()].pb(x);
                        a[dem]=s3;
                        b[dem]=x;
                        cost[dem]=get(1,x)-get(1,s3);
                        dem++;
                        de=1;
                    }
                    break;
                }
            }
            if(de) break;
        }
    }
}/*
int a, b;
void phongbeo()
{
    cin>>N>>Q>>S;
    for (int i = 0; i < N - 1; i++)
    {
        cin>>a>>b>>w;
        a--;
        b--;
        adjlist[a].push_back(make_pair(b, w));
        adjlist[b].push_back(make_pair(a, w));
        edgelist.push_back(make_pair(make_pair(min(a, b) + 1, max(a, b) + 1), w));
    }
    sort(edgelist.begin(), edgelist.end());
    memset(twok, -1, sizeof(twok));
    dfs(0, -1, 0, 0);
    int A[N-1], B[N-1], W[N-1];
    memset(A, 0, sizeof(A));
    memset(B, 0, sizeof(B));
    memset(W, 0, sizeof(W));
    find_roads(N, Q, A, B, W);
    for (int i = 0; i < N-1; i++) user_edgelist.push_back(make_pair(make_pair(min(A[i], B[i]), max(A[i], B[i])), W[i]));
    sort(user_edgelist.begin(), user_edgelist.end());
    if (edgelist != user_edgelist)
    {
        printf("Wrong Answer: Reported list of edges differ from actual.\n");
        exit(0);
    }
    if (S <= 4)
    {
        printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
        exit(0);
    }
    else
    {
        if (curQ <= target) printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
        else if (curQ >= 12000) printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (10.0-10.0*((double)(curQ - 12000) / 13000)) / 43 * 100, curQ, Q);
        else printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (40.0-30.0*((double)(curQ - target) / (12000 - target))) / 43 * 100, curQ, Q);
    }
}
*/

컴파일 시 표준 에러 (stderr) 메시지

citymapping.cpp:26:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   26 | const int inf=1e18;
      |               ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 14.11 / 43