QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#245558#5492. Toll Roadsmomen159#WA 188ms69912kbC++144.4kb2023-11-10 01:50:052023-11-10 01:50:06

Judging History

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

  • [2023-11-10 01:50:06]
  • 评测
  • 测评结果:WA
  • 用时:188ms
  • 内存:69912kb
  • [2023-11-10 01:50:05]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define momen ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define ld long double
#define fp(n) for(int i=0;i<n;i++)
#define fp1(n) for(int i=1;i<=n;i++)
#define all(v) v.begin() , v.end()
const int mod = 1e9 + 7, N = 2e5 + 5, M = 8e6 + 5;
const ll LG = 20, inf = 1e9 + 6;


int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};


pair<int,int> anc[N][20], p[N] ;
int d[N], n, q ;
vector<pair<int ,int>> adj[N];

void dfs(int i, int par , int c)
{
    p[i] = {par ,c};
    d[i] = d[par]+1;
    for(auto e:adj[i])
    {
        if(e.first == par)
            continue;
        dfs(e.first, i , e.second);
    }
}

//need par, depth
void preprocess()
{
    // k is 2^k anc
    for(int k=0;k<LG; k++)
    {
        for(int i=1; i<=n; i++)
        {
            if(k == 0)
                anc[i][k] = p[i];
            else {
                anc[i][k].first = anc[anc[i][k - 1].first][k - 1].first;
                anc[i][k].second = max(anc[anc[i][k - 1].first][k - 1].second, anc[i][k - 1].second);
            }
        }
    }
}

pair<int ,int> binaryLift(int x, int jump)
{
    int mx  =  0 ;
    for(int b=0; b<LG; b++)
    {
        if( jump & (1 << b)) {
            mx = max(mx , anc[x][b].second ) ;
            x = anc[x][b].first;
        }
    }
    return {x, mx};
}
int LCA(int a, int b)
{
    if(d[a] > d[b])
        swap(a, b);

    // guaranteed that b is deeper
    //make same depth
    int diff = d[b] - d[a];
    int mx = 0 ;
    tie(b,mx) = binaryLift(b, diff);

    if(a == b)
        return mx;

    for(int bit=LG-1; bit>=0; bit--)
    {
        if(anc[a][bit].first==anc[b][bit].first)
            continue;
        mx = max({mx ,anc[a][bit].second , anc[b][bit].second}) ;
        a = anc[a][bit].first;
        b = anc[b][bit].first;
    }
    return max(mx, p[a].second);
}



struct DSU{
    vector<int>par ;
    vector<int>sze ;
    int mx = 1;
    DSU(int n){
        par.resize(n+1) ;
        sze.resize(n+1) ;
        fp(n+1) {
            par[i]= i ;
            sze[i]= 1;
        }
    }
    int find(int a){
        while(par[a] != a ){
            a = par[a] ;
        }
        return a;
    }
    bool unite(int a , int b ){
        a = find(a) ;
        b = find(b) ;
        if (a==b)
            return 1 ;
        if (sze[a] < sze[b])
            swap(a,b) ;
        par[b] = par[a] ;
        sze[a]+=sze[b] ;
        return 0 ;
    }
};



void solve(int z) {
    int m , q;
    cin>>n>>m>>q;
    vector<pair<int ,pair<int ,int>>> edges ;
    for (int i = 0; i < m; ++i) {
        int a,b,c ;
        cin>>a>>b>>c;
        edges.push_back({c,{a,b}}) ;
    }
    sort(all(edges)) ;
    DSU d(n+1) ;
    for (int i = 0; i < m; ++i) {
        int a ,b,c ;
        c = edges[i].first , a = edges[i].second.first , b = edges[i].second.second;
        if (d.unite(a,b))
            continue;
        adj[a].push_back({b,c}) ,adj[b].push_back({a,c}) ;
    }
    dfs(1,0,0) ;
    preprocess() ;

    vector<pair<int ,int>>qu[N] ;

    for (int i = 1; i <= q; ++i) {
        int a,b ;
        cin>>a>>b ;
        int x = LCA(a,b) ;
        qu[x].push_back({i , a}) ;
    }
    DSU d2(n+1) ;
    vector<pair<int ,int>>ans(q+1) ;

    for (int i = 0; i < m; ++i) {
        int a ,b,c ;
        c = edges[i].first , a = edges[i].second.first , b = edges[i].second.second;
        if (i && c > edges[i-1].first){
            for (int j = 0; j < qu[edges[i-1].first].size(); ++j) {
                int z = qu[edges[i-1].first][j].second ;
                int y =d2.find(z) ;
                int size = d2.sze[y] ;
                ans[qu[edges[i-1].first][j].first] = {edges[i-1].first ,size };
            }
        }
        if (d2.unite(a,b))
            continue;
    }
    for (int j = 0; j < qu[edges.back().first].size(); ++j) {
        ans[qu[edges.back().first][j].first] = {edges.back().first ,d2.sze[d2.find(qu[edges.back().first][j].second)]  };
    }

    for (int i = 1; i <=q ; ++i) {
        cout<<ans[i].first<<" "<<ans[i].second<<endl ;
    }

}


int main() {
    momen
    int t = 1;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
//    cin >> t;

    for (int i = 1; i <= t; ++i) {
        //cout<<"Case #"<<i<<": ";
        solve(t);
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 15876kb

input:

4 3 6
1 2 1
2 3 3
3 4 2
1 2
1 3
1 4
2 3
2 4
3 4

output:

1 2
3 4
3 4
3 4
3 4
2 2

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 188ms
memory: 69912kb

input:

200000 199999 200000
40203 148773 165038
148773 54931 77889
54931 9912 192188
9912 180491 24730
180491 77332 36976
77332 43929 146532
43929 43341 172446
43341 141304 121793
141304 105828 148202
105828 72010 107746
72010 152016 156358
152016 150074 115703
150074 117105 73900
117105 57831 59264
57831 ...

output:

165038 3
77889 2
192188 41
24730 2
36976 3
146532 4
172446 20
121793 2
148202 4
107746 2
156358 10
115703 6
73900 5
59264 2
67443 4
26999 2
156979 16
80963 3
56618 2
107615 6
63765 3
19719 2
178439 35
95141 5
72029 4
14650 2
21437 3
109944 6
139220 7
141978 9
102949 2
170997 15
100704 3
75249 2
1312...

result:

ok 200000 lines

Test #3:

score: -100
Wrong Answer
time: 182ms
memory: 68572kb

input:

200000 199999 200000
25566 162429 116811
162429 150239 28436
150239 75366 140258
75366 176680 111452
176680 158813 50710
158813 125248 118834
125248 191706 31210
191706 163115 65321
163115 46167 44831
46167 129128 79156
129128 112971 51160
112971 195397 1773
195397 196884 159329
196884 188278 191759...

output:

116811 3
28436 2
140258 13
118834 10
118834 10
118834 10
191759 21
159329 14
79156 7
159329 14
191759 21
159329 14
159329 14
191759 21
95051 2
197843 41
46441 2
197843 41
197843 41
197843 41
197843 41
179891 15
173651 10
132452 7
179891 15
84295 3
179891 15
173651 10
179891 15
179891 15
179891 15
18...

result:

wrong answer 176367th lines differ - expected: '181203 17', found: '177802 12'