oj.uz

Submission #70535

# Submission time Handle Problem Language Result Execution time Memory
70535 2018-08-23T05:29:07 Z KLPP Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 19696 KB 
#include "collapse.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
	int C=T.size();
	int Q=P.size();
	pair<pair<int,int>,int> arr[Q];
	for(int i=0;i<Q;i++){
		arr[i].first.first=W[i];
		arr[i].first.second=P[i];
		arr[i].second=i;
	}
	sort(arr,arr+Q);
	int pnt=0;
	vector<pair<int,bool> >nei[N];
	vector<pair<int,int> > ans ;
	for(int i=0;i<C;i++){
		if(T[i]==0){
			nei[X[i]].push_back(pair<int,bool>(Y[i],true));
			nei[Y[i]].push_back(pair<int,bool>(X[i],true));
		}else{
			for(int j=0;j<nei[X[i]].size();j++){
				if(nei[X[i]][j].first==Y[i]){
					nei[X[i]][j].second=false;
				}
			}for(int j=0;j<nei[Y[i]].size();j++){
				if(nei[Y[i]][j].first==X[i]){
					nei[Y[i]][j].second=false;
				}
			}
		}
		while(pnt<Q && arr[pnt].first.first==i){
			bool visited[N];
			for(int j=0;j<N;j++){
				visited[j]=false;
			}int CC=0;
			for(int strt=0;strt<N;strt++){
				if(!visited[strt]){
					visited[strt]=true;
					CC++;
					queue<int>q;
					q.push(strt);
					while(!q.empty()){
						int u=q.front();q.pop();
						for(int j=0;j<nei[u].size();j++){
							int v=nei[u][j].first;
if(nei[u][j].second && !visited[v] && !(arr[pnt].first.second>=v ^ arr[pnt].first.second>=u)){
	visited[v]=true;
	q.push(v);
}
						}
					}
				}
			}ans.push_back(pair<int,int>(arr[pnt].second,CC));
			pnt++;
		}
	}sort(ans.begin(),ans.end());
	vector<int> R;
	for(int i=0;i<Q;i++){
		R.push_back(ans[i].second);
	}
	return R;
}

Compilation message

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<nei[X[i]].size();j++){
                ~^~~~~~~~~~~~~~~~~
collapse.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    }for(int j=0;j<nei[Y[i]].size();j++){
                 ~^~~~~~~~~~~~~~~~~
collapse.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j=0;j<nei[u].size();j++){
                   ~^~~~~~~~~~~~~~
collapse.cpp:58:62: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
 if(nei[u][j].second && !visited[v] && !(arr[pnt].first.second>=v ^ arr[pnt].first.second>=u)){
                                         ~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 760 KB Output is correct
2 Correct 14 ms 824 KB Output is correct
3 Correct 12 ms 904 KB Output is correct
4 Correct 9 ms 924 KB Output is correct
5 Correct 35 ms 1348 KB Output is correct
6 Correct 137 ms 1352 KB Output is correct
7 Correct 3967 ms 1436 KB Output is correct
8 Correct 3224 ms 1560 KB Output is correct
9 Correct 3605 ms 2024 KB Output is correct
10 Correct 3571 ms 2024 KB Output is correct
11 Correct 3074 ms 2244 KB Output is correct
12 Correct 2992 ms 2244 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 6444 KB Output is correct
2 Correct 142 ms 6780 KB Output is correct
3 Correct 8268 ms 11972 KB Output is correct
4 Correct 138 ms 11972 KB Output is correct
5 Correct 8536 ms 13584 KB Output is correct
6 Correct 2867 ms 13584 KB Output is correct
7 Execution timed out 15037 ms 15352 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 15352 KB Output is correct
2 Correct 130 ms 15352 KB Output is correct
3 Correct 167 ms 15352 KB Output is correct
4 Correct 137 ms 15352 KB Output is correct
5 Correct 820 ms 15352 KB Output is correct
6 Correct 2473 ms 16524 KB Output is correct
7 Execution timed out 15033 ms 19696 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 760 KB Output is correct
2 Correct 14 ms 824 KB Output is correct
3 Correct 12 ms 904 KB Output is correct
4 Correct 9 ms 924 KB Output is correct
5 Correct 35 ms 1348 KB Output is correct
6 Correct 137 ms 1352 KB Output is correct
7 Correct 3967 ms 1436 KB Output is correct
8 Correct 3224 ms 1560 KB Output is correct
9 Correct 3605 ms 2024 KB Output is correct
10 Correct 3571 ms 2024 KB Output is correct
11 Correct 3074 ms 2244 KB Output is correct
12 Correct 2992 ms 2244 KB Output is correct
13 Correct 85 ms 6444 KB Output is correct
14 Correct 142 ms 6780 KB Output is correct
15 Correct 8268 ms 11972 KB Output is correct
16 Correct 138 ms 11972 KB Output is correct
17 Correct 8536 ms 13584 KB Output is correct
18 Correct 2867 ms 13584 KB Output is correct
19 Execution timed out 15037 ms 15352 KB Time limit exceeded
20 Halted 0 ms 0 KB -