oj.uz

Submission #129763

# Submission time Handle Problem Language Result Execution time Memory
129763 2019-07-13T07:32:35 Z Vardanyan Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 133540 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 500*1000+5;
vector<int> g[N];
vector<int> hv[N];
vector<int> pos[N];
vector<int> ans;
int st;
bool col[N];
vector<vector<int> > all;
int POS[N];
void dfs (int v, int p = -1) {
	//printf("%d!\n", v);
	if (col[v]) {
		st = v;
		//ans.clear();
		ans.push_back(v);
		return;
	}
		col[v] = 1;
//		set<int>::iterator it = g[v].begin();
		for(int i = POS[v];i<g[v].size();i++){
			int to = g[v][i];
			if (to != p && hv[v][i]) {
				dfs(to, v);
			//	g[v].erase(g[v].find(to));
				//g[to].erase(g[to].find(v));
				//mp[v][to] = mp[to][v] = 0;
				hv[v][i] = 0;
				hv[to][pos[v][i]] = 0;
				POS[v]++;
				if (v != st) {
					ans.push_back(v);
					break;
				}
				else {
					all.push_back(ans);
					ans.clear();
					//return;
				}
			}
		}
        col[v] = 0;
}

int main(){
   // ios_base::sync_with_stdio(false);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
        //mp[x][y] = 1;
       // mp[y][x] = 1;
        hv[x].push_back(1);
        hv[y].push_back(1);
        pos[x].push_back(g[y].size()-1);
        pos[y].push_back(g[x].size()-1);
    }
   // cout<<endl;
   vector<int> v;
   for(int i = 1;i<=n;i++) v.push_back(i);
  // random_shuffle(v.begin(),v.end());
    for(int j = 0;j<n;j++){
        int i = v[j];
        /*if(i == 2){
            cout<<0<<endl;
        }*/
       /* num++;
        now.clear();
        ans.clear();
        now.push_back(i);*/
        dfs(i);
        /*if(!ans.size()) continue;
        for(int i = 0;i<ans.size()-1;i++){
            cout<<ans[i]<<" ";
            int x = ans[i];
            int y = ans[i+1];
            g[x].erase(g[x].find(y));
            g[y].erase(g[y].find(x));
        }*/
       // cout<<endl;
    }
    for(int i = 0;i<all.size();i++){
        if(!all[i].size()) continue;
        for(int j = 0;j<all[i].size();j++) printf("%d ",all[i][j]);
        printf("\n");
    }
    return 0;
}

Compilation message

postmen.cpp: In function 'void dfs(int, int)':
postmen.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = POS[v];i<g[v].size();i++){
                      ~^~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<all.size();i++){
                   ~^~~~~~~~~~~
postmen.cpp:88:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<all[i].size();j++) printf("%d ",all[i][j]);
                       ~^~~~~~~~~~~~~~
postmen.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
postmen.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35560 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 27 ms 35584 KB Output is correct
4 Correct 28 ms 35840 KB Output is correct
5 Correct 24 ms 35584 KB Output is correct
6 Correct 28 ms 35840 KB Output is correct
7 Correct 33 ms 36352 KB Output is correct
8 Correct 31 ms 35960 KB Output is correct
9 Correct 101 ms 39288 KB Output is correct
10 Correct 28 ms 35840 KB Output is correct
11 Correct 32 ms 35840 KB Output is correct
12 Correct 101 ms 39892 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35560 KB Output is correct
2 Correct 25 ms 35576 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 30 ms 35892 KB Output is correct
5 Correct 30 ms 35560 KB Output is correct
6 Correct 26 ms 35712 KB Output is correct
7 Correct 37 ms 36344 KB Output is correct
8 Correct 32 ms 35944 KB Output is correct
9 Correct 92 ms 39288 KB Output is correct
10 Correct 28 ms 35856 KB Output is correct
11 Correct 28 ms 35840 KB Output is correct
12 Correct 91 ms 39776 KB Output is correct
13 Correct 204 ms 55152 KB Output is correct
14 Correct 190 ms 45412 KB Output is correct
15 Correct 179 ms 45764 KB Output is correct
16 Correct 217 ms 55152 KB Output is correct
17 Correct 194 ms 45556 KB Output is correct
18 Correct 194 ms 47608 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 35584 KB Output is correct
2 Correct 23 ms 35600 KB Output is correct
3 Correct 25 ms 35560 KB Output is correct
4 Correct 26 ms 35840 KB Output is correct
5 Correct 26 ms 35636 KB Output is correct
6 Correct 27 ms 35832 KB Output is correct
7 Correct 31 ms 36352 KB Output is correct
8 Correct 26 ms 35968 KB Output is correct
9 Correct 86 ms 39288 KB Output is correct
10 Correct 28 ms 35888 KB Output is correct
11 Correct 32 ms 35840 KB Output is correct
12 Correct 97 ms 39776 KB Output is correct
13 Correct 214 ms 55268 KB Output is correct
14 Correct 172 ms 45268 KB Output is correct
15 Correct 169 ms 45824 KB Output is correct
16 Correct 200 ms 55152 KB Output is correct
17 Correct 202 ms 45676 KB Output is correct
18 Correct 215 ms 47500 KB Output is correct
19 Execution timed out 1036 ms 133540 KB Time limit exceeded
20 Halted 0 ms 0 KB -