oj.uz

Submission #124788

# Submission time Handle Problem Language Result Execution time Memory
124788 2019-07-04T02:00:47 Z model_code Railway (BOI17_railway) C++17
100 / 100
 235 ms 34032 KB 
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>

using namespace std;

int n, m, k, myClock;

//indexed by n
vector<vector<int> > T, ID, ministersInCity; //   ,ministersForWhichThisCityIsImportant;
vector<bool> onDFSStack;
vector<int> pre, post, val;
vector<vector<pair<int, int> > > importantCityList; 

  
//indexed by m
vector<vector<int> > importantCitiesOfMinister;
vector<int> possibleRootOfMinister;

//general
vector<int> importantTracks, DFSStack;

// DEBUGGING
void printvec(string s, vector<int> v) {
	cout << s;
	for(int i = 0; i < v.size(); ++i) cout << " " << v[i];
	cout << endl;
} 

void printvecvec(string s, vector<vector<int> > v) {
	cout << s << endl;
	for(int i = 0; i < v.size(); ++i) {
		cout << i;
		printvec(":", v[i]);
	}
}	




void initialize() {
 	scanf("%d%d%d", &n, &m, &k);
   	
	onDFSStack = vector<bool> (n, false);
	pre = vector<int> (n, 0);
	post = vector<int> (n, 0);
	val = vector<int> (n, 0);
    	
	T = vector<vector<int> > (n, vector<int>());
	ID = vector<vector<int> > (n, vector<int>());
	ministersInCity = vector<vector<int> > (n, vector<int>());
    
	// for each city, a list of pairs (minister for which this city is important, ID of this city in that ministers important city list)
	importantCityList = vector<vector<pair<int, int> > > (n, vector<pair<int, int> > ());

   	for(int i = 1; i <= n-1; ++i) {
   		int u, v;
		scanf("%d%d", &u, &v);
   		T[--u].push_back(--v);
   		T[v].push_back(u);
   		ID[u].push_back(i);
   		ID[v].push_back(i);
   	}
	
	possibleRootOfMinister = vector<int> (m, -1);
	importantCitiesOfMinister = vector<vector<int> > (m, vector<int>());
	
   	for(int i = 0; i < m; ++i) {
   		int si;
		scanf("%d", &si);
    	for(int j = 0; j < si; ++j) {
    		int city;
			scanf("%d", &city);
			ministersInCity[--city].push_back(i);
    	}
   	}
}

// prePostDFS
void prePostDFS(int pos) {
	pre[pos] = ++myClock;
	onDFSStack[pos] = true;

	for(int i = 0; i < T[pos].size(); ++i) {
		int ch = T[pos][i];
   		if(onDFSStack[ch]) continue;
		prePostDFS(ch);
   	}
   	
	onDFSStack[pos] = false;
   	post[pos] = ++myClock;
}

void importantCityDFS(int pos) {
	onDFSStack[pos] = true;
	
	for(int i = 0; i < ministersInCity[pos].size(); ++i) {
		int minister = ministersInCity[pos][i];
		while(!importantCitiesOfMinister[minister].empty() && post[importantCitiesOfMinister[minister].back()] > pre[pos]) {
			importantCitiesOfMinister[minister].pop_back(); }
		importantCitiesOfMinister[minister].push_back(pos);
	}
	
	for(int i = 0; i < T[pos].size(); ++i) {
		int ch = T[pos][i];
   		if(onDFSStack[ch]) continue;
		importantCityDFS(ch);
   	}
	
	for(int i = 0; i < ministersInCity[pos].size(); ++i) {
		int minister = ministersInCity[pos][i];
		possibleRootOfMinister[minister] = pos;
	}
	
	onDFSStack[pos] = false;
}

void setPositiveValues() {
	for(int i = 0; i < m; ++i) {
		for(int j = 0; j < importantCitiesOfMinister[i].size(); ++j) {
			val[importantCitiesOfMinister[i][j]]++;
	}}
}

void setImportantCityList() {
	for(int i = 0; i < m; ++i) {
		for(int j = 0; j < importantCitiesOfMinister[i].size(); ++j) {
			int thisCity = importantCitiesOfMinister[i][j];
			importantCityList[thisCity].push_back(pair<int, int> (i, j));
	}}
}

bool isAncestorOf(int possibleParent, int possibleChild) {return post[possibleParent] > post[possibleChild];}

// computes the LCA of DFSStack[pos] and targetCity, assuming the LCA is abovr or equal to pos on the DFSStack,
// and below (bigger than) or including lb.
int LCA(int pos, int lb, int targetCity) {
	int city = DFSStack[pos];
	//cout << "LCA(" << pos << " " << lb << " " << targetCity << ")" << endl;
	if(lb + 1 >= pos) {
		if(isAncestorOf(city, targetCity)) return city;
		return DFSStack[lb];
	}
	int test = (pos + lb) / 2;
	int testCity = DFSStack[test];
	if(isAncestorOf(testCity, targetCity)) {return LCA(pos, test, targetCity);} 
	return LCA(test, lb, targetCity);
}

void setNegativeValueDFS(int pos) {
	DFSStack.push_back(pos);
	onDFSStack[pos] = true;

	for(int i = 0; i < importantCityList[pos].size(); ++i) {
		int minister = importantCityList[pos][i].first;
		int j = importantCityList[pos][i].second;
		if(j + 1 == importantCitiesOfMinister[minister].size()) continue;
		int nextCity = importantCitiesOfMinister[minister][j+1];
		
		// LCA of pos and nextCity:
		int stackSize = DFSStack.size();
		
		//cout << "computing LCA of " << pos << " " << " and " << nextCity << endl; 
		int minusPos = LCA(stackSize - 1, 0, nextCity);
		
		// update possible root of minister
		if(post[minusPos] > post[possibleRootOfMinister[minister]]) possibleRootOfMinister[minister] = minusPos;
		
		// decrease value!
		//cout << "decreasing city # " << minusPos << " for minister " << minister << endl;
		val[minusPos]--;
	}
	
	for(int i = 0; i < T[pos].size(); ++i) {
		int ch = T[pos][i];
   		if(onDFSStack[ch]) continue;
		setNegativeValueDFS(ch);
   	}
	
	onDFSStack[pos] = false;
	DFSStack.pop_back();
}

void setNegativeRootValues() {
	for(int i = 0; i < m; ++i) {val[possibleRootOfMinister[i]]--;}
}

int findTargetEdgeDFS(int pos, int edgeID) {
	onDFSStack[pos] = true;
	
	int myVal = val[pos];
	for(int i = 0; i < T[pos].size(); ++i) {
		int ch = T[pos][i];
		int chID = ID[pos][i];
   		if(onDFSStack[ch]) continue;
		myVal += findTargetEdgeDFS(ch, chID);
   	}
	
	//cout << "pos " << pos << " myVal " << myVal << endl;
	if(myVal >= k) importantTracks.push_back(edgeID);
	
	onDFSStack[pos] = false;
	return myVal;
}
    
int main() {
   	initialize();
	
	//printvecvec("T:", T);
	//printvecvec("Ministers In City:", ministersInCity);

	prePostDFS(0);
	importantCityDFS(0);
	
	//printvecvec("Important Cities", importantCitiesOfMinister);
	
	setPositiveValues();
	//printvec("Only positive values: ", val);

	setImportantCityList();

	setNegativeValueDFS(0);
	//printvec("Values after removing LCA's: ", val);
	
	//printvec("Roots", possibleRootOfMinister);
	
	setNegativeRootValues();

	//printvec("Values: ", val);
	
	int dummy = findTargetEdgeDFS(0, -1);
	
   	sort(importantTracks.begin(), importantTracks.end());
    printf("%d\n", importantTracks.size());	
   	
   	for(int i = 0; i + 1 < importantTracks.size(); ++i) {printf("%d ", importantTracks[i]);}		
	if(importantTracks.size() != 0) {
		printf("%d\n", importantTracks[importantTracks.size() - 1]); 
	} 
}

Compilation message

railway.cpp: In function 'void printvec(std::__cxx11::string, std::vector<int>)':
railway.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); ++i) cout << " " << v[i];
                 ~~^~~~~~~~~~
railway.cpp: In function 'void printvecvec(std::__cxx11::string, std::vector<std::vector<int> >)':
railway.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); ++i) {
                 ~~^~~~~~~~~~
railway.cpp: In function 'void prePostDFS(int)':
railway.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < T[pos].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'void importantCityDFS(int)':
railway.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ministersInCity[pos].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < T[pos].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~
railway.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ministersInCity[pos].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'void setPositiveValues()':
railway.cpp:121:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < importantCitiesOfMinister[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'void setImportantCityList()':
railway.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < importantCitiesOfMinister[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'void setNegativeValueDFS(int)':
railway.cpp:155:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < importantCityList[pos].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:158:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j + 1 == importantCitiesOfMinister[minister].size()) continue;
      ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:175:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < T[pos].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'int findTargetEdgeDFS(int, int)':
railway.cpp:193:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < T[pos].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:235:42: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", importantTracks.size()); 
                    ~~~~~~~~~~~~~~~~~~~~~~^
railway.cpp:237:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < importantTracks.size(); ++i) {printf("%d ", importantTracks[i]);}  
                    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:232:6: warning: unused variable 'dummy' [-Wunused-variable]
  int dummy = findTargetEdgeDFS(0, -1);
      ^~~~~
railway.cpp: In function 'void initialize()':
railway.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &m, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~
railway.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &si);
   ~~~~~^~~~~~~~~~~
railway.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &city);
    ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 2168 KB Output is correct
3 Correct 10 ms 2044 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 11 ms 2680 KB Output is correct
7 Correct 11 ms 2428 KB Output is correct
8 Correct 9 ms 2268 KB Output is correct
9 Correct 9 ms 2296 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 2168 KB Output is correct
3 Correct 10 ms 2044 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 11 ms 2680 KB Output is correct
7 Correct 11 ms 2428 KB Output is correct
8 Correct 9 ms 2268 KB Output is correct
9 Correct 9 ms 2296 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 35 ms 3576 KB Output is correct
16 Correct 39 ms 3676 KB Output is correct
17 Correct 37 ms 3704 KB Output is correct
18 Correct 11 ms 2680 KB Output is correct
19 Correct 11 ms 2296 KB Output is correct
20 Correct 42 ms 4856 KB Output is correct
21 Correct 43 ms 4848 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 10 ms 2168 KB Output is correct
24 Correct 11 ms 2168 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 11 ms 2684 KB Output is correct
28 Correct 11 ms 2296 KB Output is correct
29 Correct 9 ms 2300 KB Output is correct
30 Correct 9 ms 2296 KB Output is correct
31 Correct 2 ms 256 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2 ms 256 KB Output is correct
35 Correct 2 ms 376 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 33984 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 172 ms 33748 KB Output is correct
4 Correct 200 ms 33204 KB Output is correct
5 Correct 144 ms 30316 KB Output is correct
6 Correct 133 ms 30036 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 26484 KB Output is correct
2 Correct 172 ms 22436 KB Output is correct
3 Correct 184 ms 22236 KB Output is correct
4 Correct 174 ms 22068 KB Output is correct
5 Correct 195 ms 22196 KB Output is correct
6 Correct 147 ms 26640 KB Output is correct
7 Correct 142 ms 26492 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 26484 KB Output is correct
2 Correct 172 ms 22436 KB Output is correct
3 Correct 184 ms 22236 KB Output is correct
4 Correct 174 ms 22068 KB Output is correct
5 Correct 195 ms 22196 KB Output is correct
6 Correct 147 ms 26640 KB Output is correct
7 Correct 142 ms 26492 KB Output is correct
8 Correct 162 ms 26604 KB Output is correct
9 Correct 164 ms 26476 KB Output is correct
10 Correct 140 ms 30068 KB Output is correct
11 Correct 132 ms 29936 KB Output is correct
12 Correct 121 ms 22524 KB Output is correct
13 Correct 135 ms 22492 KB Output is correct
14 Correct 161 ms 19932 KB Output is correct
15 Correct 180 ms 20048 KB Output is correct
16 Correct 177 ms 22192 KB Output is correct
17 Correct 171 ms 22184 KB Output is correct
18 Correct 172 ms 22136 KB Output is correct
19 Correct 181 ms 22520 KB Output is correct
20 Correct 149 ms 26740 KB Output is correct
21 Correct 153 ms 26872 KB Output is correct
22 Correct 190 ms 26868 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 2168 KB Output is correct
3 Correct 10 ms 2044 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 11 ms 2680 KB Output is correct
7 Correct 11 ms 2428 KB Output is correct
8 Correct 9 ms 2268 KB Output is correct
9 Correct 9 ms 2296 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 35 ms 3576 KB Output is correct
16 Correct 39 ms 3676 KB Output is correct
17 Correct 37 ms 3704 KB Output is correct
18 Correct 11 ms 2680 KB Output is correct
19 Correct 11 ms 2296 KB Output is correct
20 Correct 42 ms 4856 KB Output is correct
21 Correct 43 ms 4848 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 10 ms 2168 KB Output is correct
24 Correct 11 ms 2168 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 11 ms 2684 KB Output is correct
28 Correct 11 ms 2296 KB Output is correct
29 Correct 9 ms 2300 KB Output is correct
30 Correct 9 ms 2296 KB Output is correct
31 Correct 2 ms 256 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2 ms 256 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 174 ms 33984 KB Output is correct
37 Correct 2 ms 256 KB Output is correct
38 Correct 172 ms 33748 KB Output is correct
39 Correct 200 ms 33204 KB Output is correct
40 Correct 144 ms 30316 KB Output is correct
41 Correct 133 ms 30036 KB Output is correct
42 Correct 140 ms 26484 KB Output is correct
43 Correct 172 ms 22436 KB Output is correct
44 Correct 184 ms 22236 KB Output is correct
45 Correct 174 ms 22068 KB Output is correct
46 Correct 195 ms 22196 KB Output is correct
47 Correct 147 ms 26640 KB Output is correct
48 Correct 142 ms 26492 KB Output is correct
49 Correct 162 ms 26604 KB Output is correct
50 Correct 164 ms 26476 KB Output is correct
51 Correct 140 ms 30068 KB Output is correct
52 Correct 132 ms 29936 KB Output is correct
53 Correct 121 ms 22524 KB Output is correct
54 Correct 135 ms 22492 KB Output is correct
55 Correct 161 ms 19932 KB Output is correct
56 Correct 180 ms 20048 KB Output is correct
57 Correct 177 ms 22192 KB Output is correct
58 Correct 171 ms 22184 KB Output is correct
59 Correct 172 ms 22136 KB Output is correct
60 Correct 181 ms 22520 KB Output is correct
61 Correct 149 ms 26740 KB Output is correct
62 Correct 153 ms 26872 KB Output is correct
63 Correct 190 ms 26868 KB Output is correct
64 Correct 167 ms 27912 KB Output is correct
65 Correct 235 ms 24440 KB Output is correct
66 Correct 211 ms 22412 KB Output is correct
67 Correct 196 ms 21624 KB Output is correct
68 Correct 148 ms 21212 KB Output is correct
69 Correct 124 ms 21240 KB Output is correct
70 Correct 172 ms 28084 KB Output is correct
71 Correct 160 ms 26500 KB Output is correct
72 Correct 2 ms 380 KB Output is correct
73 Correct 11 ms 2168 KB Output is correct
74 Correct 12 ms 2040 KB Output is correct
75 Correct 2 ms 376 KB Output is correct
76 Correct 2 ms 376 KB Output is correct
77 Correct 11 ms 2680 KB Output is correct
78 Correct 11 ms 2296 KB Output is correct
79 Correct 9 ms 2296 KB Output is correct
80 Correct 10 ms 2296 KB Output is correct
81 Correct 2 ms 376 KB Output is correct
82 Correct 2 ms 376 KB Output is correct
83 Correct 2 ms 376 KB Output is correct
84 Correct 2 ms 256 KB Output is correct
85 Correct 2 ms 376 KB Output is correct
86 Correct 36 ms 3576 KB Output is correct
87 Correct 36 ms 3676 KB Output is correct
88 Correct 36 ms 3704 KB Output is correct
89 Correct 11 ms 2808 KB Output is correct
90 Correct 12 ms 2296 KB Output is correct
91 Correct 42 ms 4984 KB Output is correct
92 Correct 43 ms 4856 KB Output is correct
93 Correct 2 ms 376 KB Output is correct
94 Correct 169 ms 34032 KB Output is correct
95 Correct 167 ms 33772 KB Output is correct
96 Correct 156 ms 33108 KB Output is correct
97 Correct 142 ms 30324 KB Output is correct
98 Correct 132 ms 30004 KB Output is correct
99 Correct 196 ms 22416 KB Output is correct
100 Correct 184 ms 22208 KB Output is correct
101 Correct 176 ms 22136 KB Output is correct
102 Correct 171 ms 22520 KB Output is correct
103 Correct 151 ms 26716 KB Output is correct
104 Correct 151 ms 26872 KB Output is correct
105 Correct 147 ms 26484 KB Output is correct
106 Correct 158 ms 26620 KB Output is correct
107 Correct 156 ms 26620 KB Output is correct
108 Correct 132 ms 29908 KB Output is correct
109 Correct 132 ms 29852 KB Output is correct
110 Correct 128 ms 22700 KB Output is correct
111 Correct 128 ms 22492 KB Output is correct
112 Correct 172 ms 20004 KB Output is correct
113 Correct 168 ms 19964 KB Output is correct