oj.uz

답안 #433779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433779 2021-06-20T10:43:36 Z oscar1f 다리 (APIO19_bridges) C++17
14 / 100
 294 ms 5392 KB 
#include<bits/stdc++.h>
using namespace std;
 
const int MAX_SOMMET=50*1000+1;
int nbIles,nbPonts,deb,fin,poids,nbReq,typeReq;
tuple<int,int,int> pos;
vector<tuple<int,int,int>> req; 
vector<pair<int,int>> reponse;
int pere[MAX_SOMMET],prof[MAX_SOMMET];

int find(int pers) {
    if (pere[pers]!=pers) {
        pere[pers]=find(pere[pers]);
    }
    return pere[pers];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin>>nbIles>>nbPonts;
	for (int i=1;i<=nbPonts;i++) {
		cin>>deb>>fin>>poids;
        req.push_back(make_tuple(poids,deb,fin));
	}
	cin>>nbReq;
	for (int ireq=1;ireq<=nbReq;ireq++) {
		cin>>typeReq>>deb>>poids;
		req.push_back(make_tuple(poids,-deb,ireq));
	}
    sort(req.begin(),req.end());
    for (int i=1;i<=nbIles;i++) {
        pere[i]=i;
        prof[i]=1;
    }
    while (req.size()>0) {
        pos=req.back();
        req.pop_back();
        //cout<<get<0>(pos)<<" "<<get<1>(pos)<<" "<<get<2>(pos)<<" ";
        if (get<1>(pos)>0) {
            deb=find(get<1>(pos));
            fin=find(get<2>(pos));
            if (deb!=fin) {
                pere[fin]=deb;
                prof[deb]+=prof[fin];
            }
            //cout<<prof[1]<<" "<<prof[2]<<" "<<prof[3]<<endl;
        }
        else {
            reponse.push_back(make_pair(get<2>(pos),prof[find(-get<1>(pos))]));
            //cout<<reponse.back().second<<" "<<find(-get<1>(pos))<<endl;

        }
    }
    sort(reponse.begin(),reponse.end());
    for (int i=0;i<nbReq;i++) {
        cout<<reponse[i].second<<endl;
    }
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 237 ms 4656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 238 ms 4164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 5264 KB Output is correct
2 Correct 208 ms 3492 KB Output is correct
3 Correct 64 ms 1988 KB Output is correct
4 Correct 70 ms 1884 KB Output is correct
5 Correct 264 ms 5368 KB Output is correct
6 Correct 268 ms 5256 KB Output is correct
7 Correct 253 ms 5320 KB Output is correct
8 Correct 238 ms 4396 KB Output is correct
9 Correct 242 ms 4524 KB Output is correct
10 Correct 233 ms 4748 KB Output is correct
11 Correct 294 ms 4756 KB Output is correct
12 Correct 250 ms 4752 KB Output is correct
13 Correct 253 ms 4972 KB Output is correct
14 Correct 265 ms 5392 KB Output is correct
15 Correct 261 ms 5356 KB Output is correct
16 Correct 269 ms 5384 KB Output is correct
17 Correct 269 ms 5192 KB Output is correct
18 Correct 262 ms 5168 KB Output is correct
19 Correct 262 ms 5272 KB Output is correct
20 Correct 254 ms 5172 KB Output is correct
21 Correct 254 ms 5140 KB Output is correct
22 Correct 268 ms 5372 KB Output is correct
23 Correct 246 ms 5072 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 237 ms 4656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -